[백준] [DP] 1309. 동물원

1309. 동물원

 

 

• 풀이 1
  • 왼쪽, 오른쪽만 나눠서 생각했는데 아무것도 선택하지 않는 경우도 하나의 열로 만들어두면 편함
  • 아무것도 선택안하는 경우 -> 이전 칸의 모든 경우 다 가능
  • 왼쪽 칸 선택하는 경우 -> 이전 칸에서 오른쪽 칸 선택하는 경우/ 아예 선택 안 하는 경우 2가지 가능
  • 오른쪽 칸 선택하는 경우 -> 이전 칸에서 왼쪽 칸 선택하는 경우/ 아예 선택 안 하는 경우 2가지 가능

n = int(input())
dp = [[0, 0, 0] for _ in range(n+1)]
dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1

for i in range(2, n+1):
    # 아무것도 선택 안하는 경우
    dp[i][0] = (sum(dp[i-1])) % 9901
    # 왼쪽 칸 선택
    dp[i][1] = (dp[i-1][0]+dp[i-1][2]) % 9901
    # 오른 칸 선택
    dp[i][2] = (dp[i-1][0]+dp[i-1][1]) % 9901

print((sum(dp[n])) % 9901)

 

• 다른 사람 풀이
  • 놓고/ 안놓고 2가지 경우로 생각 ☞ 두 가지는 배반사건이므로 +
  • 현재 i 칸에 놓을 경우
    • 이전 i-1 칸에 놓여진 경우 →  i-1에 놓여진 경우에 하나씩 붙기 때문에 개수 동일 
    • 이전 i-1 칸에 안 놓여진 경우 → 안놓아진 경우에 현재 i의 왼/오 2가지 경우 ☞ x2
  • 현재 i 칸에 안놓는 경우
    • 이전 i-1칸에 놓여지든,안놓여지든 상관없이 다 가능 ☞ sum(dp[i-1])

n = int(input())
dp = [[0, 0] for _ in range(n+1)]
dp[1][0] = 2
dp[1][1] = 1

for i in range(2, n+1):
    # 놓는 경우
    dp[i][0] = (dp[i-1][0] + dp[i-1][1]*2) % 9901
    # 안 놓는 경우
    dp[i][1] = (sum(dp[i-1])) % 9901

print((sum(dp[n])) % 9901)