흙금이네 블로그

아이디어 규칙을 찾고 동적 계획법으로 가짓수를 계산한다. 풀이 고정석으로 구분된 연속된 좌석에 대해 그 가짓수가 좌석 개수에 따라 피보나치 수열을 이루고 있다. 리스트 vip에는 0과 좌석 끝 번호를 추가하여 고정석 번호를 저장하고, 리스트 dp에는 피보나치 수열을 저장한다. 전체 가짓수는 연속된 일반 좌석들의 곱이므로 결과값 res에 일반 좌석 개수에 따른 피보나치 수열의 수를 곱한다. import sys input = sys.stdin.readline def solution(): N = int(input()) M = int(input()) vip = [0]+[int(input()) for _ in range(M)]+[N+1] dp = [1]*(N+1) for i in range(2, N+1): dp[..