[백준] 1309번(동물원)

백준 1309번

최종 제출 코드

MOD = 9901

n = int(input())

dp = [1,1,1]

for j in range(n-1):
  ele1 = (dp[1] % MOD + dp[2] % MOD) % MOD
  ele2 = (dp[0] % MOD + dp[2] % MOD) % MOD
  ele3 = (dp[0] % MOD +dp[1] % MOD + dp[2] % MOD) % MOD
  dp[0] = ele1
  dp[1] = ele2
  dp[2] = ele3
  
print(sum(dp)%MOD)

◼ 각 행에서 발생할 수 있는 경우의 수를 세어 최종단계에서 모두 더한다.

• 각 행에서는 (O, X), (X, O), (X, X)의 케이스가 발생 가능
• 이번 행이 (O, X)려면 지난 행이 (X, O), (X, X) 여야 한다.
• 이번 행이 (X, O)려면 지난 행이 (O, X), (X, X) 여야 한다.
• 이번 행이 (X, X)려면 지난 행이 (O, X), (X, O), (X, X) 여야 한다.
• 각각의 경우에서 파생되는 경우의 수는 1개 이기 때문에, 이전 행에서 발생한 케이스를 더하여 dp를 갱신하면 된다.

dp[0] = dp[1] + dp[2]
dp[1] = dp[0] + dp[2]
dp[2] = dp[0] + dp[1] + dp[2]