https://acmicpc.net/problem/2302

풀이

#dp
처음에 다른 사람들이 흔히 생각하는 방법대로 생각했다가 생각이 흘러서 다른 사람들이랑 좀 다르게..? 좀 복잡하게 ..? 푼 것 같다.

내 풀이

• dp배열을 2차원 배열로 선언하여 dp[자리][0~1]로 만들었다. dp[i][0]은 i번째 자리에서 자리를 바꾸지 않은 경우의 경우의 수를, dp[i][1]은 i번째 자리에서 자리를 바꾼 경우의 수를 구해서 dp[N][0]+dp[N][1]을 출력한다.
• vip 좌석을 구분해주기 위해 dp[vip좌석 인덱스][1]을 -1로 만든다.
• i번째 좌석이 vip 좌석인 경우와 그렇지 않은 경우/ 그리고 그 안에서 i-1번째 좌석이 vip 좌석인 경우와 그렇지 않은 경우로 조건을 나누어 계산한다.

기본적으로

• 안 바꾸는 경우 : dp[i-1][0] + dp[i-1][1]

• 바꾸는 경우 : dp[i-1][0] (이전에서 이미 바꿨으면 안되니까)
  이고

vip 좌석이 앞에 있는 경우

• 안 바꾸는 경우 : dp[i-1][0]
• 바꾸는 경우 : 0

인데 vip 좌석을 -1로 표시해주었기 때문에 연산하면서 이것이 없어지지 않도록 해당 좌석이 vip 인지 아닌지도 구분해주어야 했다.

# 실버1 dp
N = int(input())
M = int(input())

default = list(int(input()) for _ in range(M))

dp = [[0]*2 for _ in range(N+1)]

dp[1][0] = 1
dp[1][1] = 0


for d in default:
    dp[d][1] = -1

for i in range(2, N+1):
    if dp[i][1] == -1:
        if dp[i-1][1] != -1:
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            dp[i][1] = -1
        else:
            dp[i][0] = dp[i - 1][0]
            dp[i][1] = -1
    else:
        if dp[i-1][1] != -1:
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            dp[i][1] = dp[i-1][0]
        else:
            dp[i][0] = dp[i-1][0]
            dp[i][1] = 0

if dp[N][1] == -1:
    print(dp[N][0])
else:
    print(dp[N][0]+dp[N][1])

다른 사람 풀이

곱의 법칙(동시에 일어남)과 합의 법칙(동시에 일어나지 않음)을 섞어서 푼다. vip 좌석을 구분점으로 vip 좌석이 아닌 좌석들을 합의 법칙으로 배치의 경우의 수를 계산하고 그 그룹들을 곱해준다.

합의 법칙의 경우 점화식 : dp[n] = dp[n-1] + dp[n-2]
dp[n] = 안 바꾼 경우 + 바꾼 경우
이다.

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
vip = [int(sys.stdin.readline()) for _ in range(m)]

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 # 1
dp[2] = 2 # 1 2, 2 1
# dp[3] = 3 # 1 2 3, 1 3 2, 2 1 3

for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]


answer = 1
if m > 0:
    pre = 0
    for j in range(m):
        answer *= dp[vip[j] - 1 - pre]
        pre = vip[j]
    answer *= dp[n - pre]
else:
    answer = dp[n]
print(answer)

결론

단순하게 생각하자(?)