[BOJ] 백준 5546번 파스타 | python 파이썬 코드, 해설, 풀이

백준 5546번 파스타 문제 파이썬 풀이입니다.

https://www.acmicpc.net/problem/5546

5546번: 파스타

너무나도 DP스러운 문제기 때문에 점화식을 찾아서 구현해주면 되는 문제입니다.

 

dp 테이블는 dp[N번째 날짜에][직전에안먹은거,직전에먹은거][파스타종류] 가 되고

fix 배열에 고정된 파스타에 대한 정보를 저장합니다.

 

 

주요코드설명

line 13~20 : 1일차에 먹는 경우를 세팅해줍니다.

 

line 22~38 : 2일차부터 N일차까지 토마토 소스, 크림 소스, 바질 소스 로 픽스된 경우와 아닌경우에 점화식에 따라 더해갑니다.

* 이때 문제 조건에 따라 10000으로 나눈 나머지를 구하며서 가면 됩니다.

 

 

전체코드

import sys
 
input = sys.stdin.readline
 
N, K = map(int, input().split())
dp = [[[0, 0, 0], [0, 0, 0]] for _ in range(N + 1)]
fix = [0 for _ in range(N + 1)]
 
for i in range(K):
    a, b = map(int, input().split())
    fix[a] = b
 
if (fix[1] == 1):
    dp[1][0] = [1, 0, 0]
elif (fix[1] == 2):
    dp[1][0] = [0, 1, 0]
elif (fix[1] == 3):
    dp[1][0] = [0, 0, 1]
else:
    dp[1][0] = [1, 1, 1]
 
for i in range(2, N + 1):
    if (fix[i] == 1):
        dp[i][0][0] = (dp[i - 1][0][1] + dp[i - 1][1][1] + dp[i - 1][0][2] + dp[i - 1][1][2]) % 10000
        dp[i][1][0] = dp[i - 1][0][0]
    elif (fix[i] == 2):
        dp[i][0][1] = (dp[i - 1][0][0] + dp[i - 1][1][0] + dp[i - 1][0][2] + dp[i - 1][1][2]) % 10000
        dp[i][1][1] = dp[i - 1][0][1]
    elif (fix[i] == 3):
        dp[i][0][2] = (dp[i - 1][0][0] + dp[i - 1][1][0] + dp[i - 1][0][1] + dp[i - 1][1][1]) % 10000
        dp[i][1][2] = dp[i - 1][0][2]
    else:
        dp[i][0][0] = (dp[i - 1][0][1] + dp[i - 1][1][1] + dp[i - 1][0][2] + dp[i - 1][1][2]) % 10000
        dp[i][1][0] = dp[i - 1][0][0]
        dp[i][0][1] = (dp[i - 1][0][0] + dp[i - 1][1][0] + dp[i - 1][0][2] + dp[i - 1][1][2]) % 10000
        dp[i][1][1] = dp[i - 1][0][1]
        dp[i][0][2] = (dp[i - 1][0][0] + dp[i - 1][1][0] + dp[i - 1][0][1] + dp[i - 1][1][1]) % 10000
        dp[i][1][2] = dp[i - 1][0][2]
 
print((sum(dp[N][0]) + sum(dp[N][1])) % 10000)