DP를 정의 하는 방법

문제

 

2302번: 극장 좌석

 

 

---

 

재정의

경우의 수를 활용하여 풀려고 하니 쉽지 않았다.

단순 곱사건(동시에 일어나는 사건)이 아니라, 합사건도 같이 일어나기 때문이다.

 

이는 완전 탐색을 요구하고, 상태 공간의 중복이 발생한다.

그냥 DP를 사용하려고 하니, 상태 공간의 정의가 마음에 들지 않았다.

손으로 작성 해 보니 어떤 상태 공간을 사용할지 찾을 수 있었다.

 

역시 DP각은 손으로 써서 봐야 잘 보인다.

 

재귀 함수로 문제 정의하기

완전 탐색을 해야함을 인지 했으니,

일단 재귀 함수로 간단하게 정의를 해보자

 

solve(seat_idx: int, picked: List[int]) -> int
seat_idx부터 자리를 앉히고, 이때까지 앉힌 인원이 picked일 때
만들 수 있는 경우의 수

 

이 단순한 정의로 DP를 하면 메모리 초과가 난다. 

비트마스크를 사용한다고 가정하고, 이 문제의 메모리 제한은 128MB이다.

 

cache = [[0] * (1<<40) for _ in range(40)]

 

정수는 4Byte니, 한 행이 사용하는 크기는 4 Byte * (1<<40) = 4.x TB라는 화끈한 값이 나오므로 사용할 수 없다.

 

---

상태 공간 가볍게 정의하기

현재 상태 공간을 직접 손으로 직접 적어보자.

상태 공간이 중복 되는것이 보이므로, DP를 쓰는 것은 자명하다.

그리고 보면, picked가 다채로운 변화를 보이지 않는다.

 

idx에서 idx를 넣게 되면, idx+1에서는 선택지가 두 개이다.

• idx +1을 넣는다.
• idx를 넣는다.

 

하지만, idx에서 idx-1을 넣게 되면 idx +1에서는 선택지가 하나 뿐이다.

• idx+1을 넣는다.

 

idx + 1에서 idx+1 밖에 넣지 못하는 이유에 대해 생각해보자.

idx에서 idx-1을 넣었다는 사실 자체가 idx <-> idx-1 교환을 했다는 것이다.

추가 적인 교환을 하게되면 1칸 교환이 아닌 2칸 교환이 되므로, 문제의 조건에 따라 불가능하다.

 

즉, 지금까지 뭐를 골랐는게 중요한게 아니다.

idx에서 재귀에 들어갔을 때, idx -1에서 변경을 했냐 안했냐가 중요한 요소이다.

• idx - 1 에서 변경을 했을 때 (idx -2을 사용 했을 때)
  
  • idx에서 idx를 사용한다 : idx를 만드는 경우의 수 == idx-1에서 만들 수 있는 경우의 수
• idx -1에서 변경을 안 했을 때 (idx - 1을 사용했을 때)
  • idx에서 idx를 사용한다 : idx를 만드는 경우의 수 = = idx-1 에서 만들 수 있는 경우의 수
  • idx에서 idx-1을 사용한다 : idx를 만드는 경우의 수 == (idx-2 에서) +  (idx-1 에서) 만들 수 있는 경우의 수

 

중복되는 부분을 고려해서 이 식을 정리하면 다음과 같다. 

idx의 경우의 수 = idx-1의 경우의 수 + idx-2의 경우의 수(idx-1을 변경을 안했다면)

이는 피보나치 수열과 동일 하게 간단한 DP로 귀결 된다.

 

 

여기서 하나 있는 문제점은 고정석이 존재 한다는 점.

그래서 피보나치 수열에서 조건을 추가로 걸어줘야 한다.

 

idx나, idx-1이 고정석이라면, 변경이 불가능 하기 때문에

고정석이거나 고정석 이전의 경우 idx-2를 만드는 경우의 수를 더하지 않아야 한다.

 

n = int(input())
cache = [None] * (n+1)
cache[0] = cache[1] = 1

book_cnt = int(input())
booked_seats = [int(input()) for _ in range(book_cnt)]


def combi_seat(idx: int) -> int: 
    if (ret := cache[idx]) is not None:
        return ret
    

    ret = combi_seat(idx-1)

    if (idx-1) not in booked_seats\
            and idx not in booked_seats:
        ret += combi_seat(idx - 2)

    cache[idx] = ret
    return ret  


print(combi_seat(n))