[python]🔥🔥🔥2302번 극장 좌석

점화식을 이해하는데에 굉장히 많은 시간이 걸렸다.

1부터 6까지 노가다를 통해

단순히 피보나치 수열처럼 An=(An-1)+(An-2)라는 점화식을 알게는 되었다.

그러나 왜 그렇게 되는지에 대해서 고민을 계속하다 결국 친구한테 물어 알게 되었다.

 

1. 도형화 하기

1,2,3,4,5와 같은 연속된 수가 있을 때 각 자리는 양 옆의 숫자랑만 바꿀 수 있다.

그리고 한번 바꾼 숫자는 다른 숫자랑 바꿀 수 없다.

숫자로 생각하기에 어려워 친구는 타일 채우기로 직관적으로 문제를 바꿨다.

 

1,2,3,4,5는 5칸짜리 빈공간이 있다고 생각한다. 그러면

2칸짜리 타일을 빈 공간에 넣을 수 있는 모든 경우의 수가 위 문제와 똑같은 경우이다.

그렇게 숫자 바꾸는것이 아닌 도형을 통해 직관적으로 생각하게 했다.

 

왜 피보나치 수열인가

2.끝부분 주목하기

예시로

1,2,3,4,5를 쪼개보면

1번째 1,2,3,4까지 자리를 바꾸고 5는 안바꾸는 경우

2번째 1,2,3자리와 5,4의 자리를 바꾸는 경우이다.

여기서 5,4의 자리를 안바꾸는 경우는 1번째 경우에 포함이 되어있다.

이것은 곧 1,2,3,4,5의 자리를 바꾸는 경우의 수는 1,2,3자리 바꾸기+1,2,3,4자리 바꾸는 경우의 수의 합과 같다.

ttl = int(input())
vips = int(input())
rrst = 1
stg = 1
def do(idx):
    a1 = 1 #피보나치 수열 첫번째
    a2 = 2 #피보나치 수열 두번째
    rst = idx #3번째 항까지 안갈때
    for i in range(3,idx+1):
        rst = a1+a2
        a1 = a2
        a2 = rst
    return rst if rst!=0 else 1
for i in range(vips):
    call = int(input())
    rrst*=do(call-stg)
    stg = call+1
rrst*=do(ttl-stg+1)  #경우의 수 문제로 vip기점으로 독립이기에 곱해준다
print(rrst)