[백준] 2302 극장좌석 (python)

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

2302번: 극장 좌석

 

 

문제설명

극장 좌석과 입장권이 있을 때, 입장권에 적힌 좌석 숫자 -1, +0, +1 인 좌석에 앉을 수 있을 때, 가능한 경우의 수는?

 

 

접근1

완전탐색 dfs로 처음에 접근했는데,  pypy3으로 해도 시간초과

N = int(input())
M = int(input()) # 고정석 개수
arr = [0]*(N+1)
fix_set = set()
for _ in range(M):
    fixed = int(input())
    arr[fixed] = fixed
    fix_set.add(fixed)

free_nums = N - len(fix_set)

result = 0
def dfs(cur_index):  # cur_index는 입장권 번호, arr의 index는 좌석번호
    global result
    if cur_index == N+1:
        result += 1
        # print(cur_index, arr)
        return

    # 자리가 고정석이면 다음 입장권 번호에 대해서, 좌석 선택
    if cur_index in fix_set:
        dfs(cur_index+1)


    if 1<= cur_index - 1 <= N:  # 한 칸 앞에 앉을 수 있는 경우
        if arr[cur_index-1] == 0:
            arr[cur_index-1] = cur_index
            dfs(cur_index+1) # 다음 좌석 번호로
            arr[cur_index-1] = 0

    if 1 <= cur_index <= N:  # 입장권에 해당하는 칸에 앉는 경우
        if arr[cur_index] == 0:
            arr[cur_index] = cur_index
            dfs(cur_index+1) # 다음 좌석 번호로
            arr[cur_index] = 0

    if 1 <= cur_index +1 <= N: # 한칸 뒷자리에 앉는 경우
        if arr[cur_index+1] == 0:
            arr[cur_index+1] = cur_index
            dfs(cur_index+1) # 다음 좌석 번호로
            arr[cur_index+1] = 0




dfs(1)
print(result)

 

 

접근2

dp를 활용 했지만, 일단 실패

 

N = int(input())
M = int(input()) # 고정석 개수
fix_lst = []
for _ in range(M):
    fixed = int(input())
    fix_lst.append(fixed)

dp = [0]*(N+1)
# 1
# 12, 21
# 123, 132, 213
# 1234, 1324, 2134, 1243, 2143
# 이처럼 dp[n] = dp[n-1] + dp[n-2] 이다

if N == 1:
    print(1)
elif N == 2:
    if M == 0 :
        print(2)
    elif M >= 1:
        print(1)
elif N >=3:
    dp[1] = 1
    dp[2] = 2
    for num in range(3,N+1):
        dp[num] = dp[num-1] + dp[num-2]

# print(dp)
# 고정석을 기준으로 앞 뒤는 서로 완전히 영향을 끼치지 못한다
# 따라서 고정석을 기준으로 분할하여 계산하면 된다

if M == 0:
    print(dp[N])
elif M == 1:
    print( dp[fix_lst[0]-1] * dp[ N-  fix_lst[-1] ] )

else:
    result = 0
    result += dp[fix_lst[0]-1]
    result *= dp[ N -  fix_lst[-1] ]

    for i in range(1,M):
        front = fix_lst[i-1]
        back = fix_lst[i]
        result *= dp[back-front-1]
    print(result)