[Python] 2302번: 극장 좌석

https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

 

# https://www.acmicpc.net/problem/2302

# 고정석은 움직이지 않되 얼마나 더 바꿀수 있는지 계산을 하는 프로그램을 만들어라

# 단 움직일수있는 범위는 자신의 왼쪽 오른쪽 1칸 뿐이니 123이 321 로 바꿀수 없다는것을 알자

# 경우의수를 파악해서 점화식을 만들어 보자

"""

1칸 1

2칸 2

3칸 3

4칸 5

.

.

.

피보나치 수열인들함 한번 재귀함수를 만들어서 풀어봐야 하나? 아님 리스트를 생성하는 식으로 풀어보자

"""

''' 실패

def fib(n):

   

    if n == 0:    #종료조건1

        return 0

    elif n==1 or n==2:    #종료조건2

        return 1

    else:

        return fib(n - 1) + fib(n - 2)    #이전항 2개를 더한다는 조건이 핵심이다.

import sys

N = int(sys.stdin.readline())

fixed = int(sys.stdin.readline())

fixed_Table = []    #고정석 좌석

for _ in range(fixed):

    fixed_Table.append(int(sys.stdin.readline()))

if fixed==0:

    print(N)

    exit(0)

# 뭉태기는 fixed+1개 존재한다고 생각한다.

뭉태기list=[]

뭉태기list.append(fixed_Table[0]-1)# 첫 fix요소 - 1

뭉태기list.append(N-fixed_Table[-1])# 마지막 좌석번호 - 끝 fix요소

for i in range(len(fixed_Table)-1):    # 2칸짜리 고정석이면 0 이렇게 들어감

    # print(fixed_Table[i+1])

    # print(fixed_Table[i])

    # print('**********')

    뭉태기list.append(fixed_Table[i+1]- fixed_Table[i]-1)

#print("뭉태기 리스트", 뭉태기list)

King=1

for _ in range(len(뭉태기list)):

    King*=fib(뭉태기list[_]+1)

print(King)

'''

import sys

n = int(sys.stdin.readline())    #좌석의 개수 입력 (1부터 시작)

m = int(sys.stdin.readline())    #고정석의 개수 입력

vip = [int(sys.stdin.readline()) for _ in range(m)]    #고정석의 좌석번호가 입력됨(1부터)

#좌석이 1개만 있는경우 출력해준다

if n==1:

    print(1)

    exit(0)

dp = [0] * (n + 1)

dp[0] = 1

dp[1] = 1 # 1

dp[2] = 2 # 1 2, 2 1

# 1 2 3 5 8 .... 인덱스번호랑 좌석번호랑 같다고 취급하면 편함

# 점화식 : dp[n] = dp[n - 1] + dp[n - 2]

for i in range(3, n + 1):    # 피보나치 수열 초기화 해줌

    dp[i] = dp[i - 1] + dp[i - 2]

answer = 1 # 경우의 수

# vip의 유무에 따라 경우의 수를 도출

if m > 0:  #고정석의 개수가 0보다 크면 실행  

    pre = 0

   

    # 반복문을 통해 vip 사이에 그룹에 들어가는 경우의 수를 확인

    for j in range(m):   #고정석 2개면 0 1 2 이렇게 들어간다.

        now = vip[j] - 1 - pre # vip좌석번호 - 시작번호 -1 에 해당하는 피보나치 수열을 사용

        answer *= dp[now]    

        pre = vip[j]    #vip의 좌석 번호가 된다.

    answer *= dp[n - pre]    #마지막 뭉텅이까지 잊지말고 넣어준다.

else:     #고정석의 개수가 0개이면 실행

    answer = dp[n]

print(answer)

 

 

<알아두어야할점>

이 문제를 통해서 다이내믹 프로그래밍(DP)가 무엇인지 알았다.

 

입력받은 n을 기준으로 그 크기만큼의 배열(리스트)를 생성해서 내가 입력한 만큼만 공간을 사용하기 때문에 메모리와 시간 둘다 효율적으로 사용할수 있다(불필요한 연산과 공간이 없다)

 

우선 첫번째로 생각해야할 알고리즘은 극장 좌석의 수에 따른 경우의수는 피보나치 수열을 따른다는 것이다. (1,1,2,3,5,8,13... n=(n-1) + (n-2) ) 규칙이 존재

 

우선 n개를 입력받은뒤, n+1개의 배열을 형성한다. (이떄 피보나치 수열의 초기 3항목인 1, 1, 2 는 직접 초기화해준다.)

이후 [3] 인덱스부터 피보나치 수열의 점화식을 활용해서 규칙에 맞게 초기화를 해준다.

 

이후 고정석 - 현재계산초기값 -1 공식을 통해서 일반좌석의 개수를 알고 피보나치 공식을 통해 계산을 한뒤 누적해서 곱해준다. (이 방식은 마지막 VIP석 이후에 일반석의 길이까지는 고려하지 않기에, pre가 마지막 vip로 남아있다는걸 활용해서 꼼꼼이 챙겨준다.)

 

마지막으로 고정석의 개수가 0개일떄, 과석의 개수가 1일때를 따로 예외처리를 해주었다.