[BOJ] 극장 좌석 in Python

문제풀러 가기!

처음에 이 문제 풀 때는 조합으로 접근했습니다. 물론 문제의 조건에 따라 연속된 좌석에 따른 앉을 수 있는 방법의 수가 정해져 있다는 것은 알고 있었습니다. 해당 방법의 수는 계차수열을 따르고 있더군요. 그래서 그렇게 접근하고 문제를 풀었으나, 몇몇 케이스는 처리하지 못하는 경우가 발생하는 바람에 다른 풀이를 참고 했습니다. 근데 역시나 계차 수열이더군요. 저는 숫자가 주어지면 그 때 계산하려고 했으나, 이 역시 프로그래밍 사고 방식에는 좋지 않음을 알게 되었습니다. 그냥 미리 계산해놓고 해당 숫자가 나오면 바로 참조하면 될텐데 그러지 못했네요. 이게 그 말로만 듣던 메모이제이션으로 생각듭니다.

문제의 아이디어는 연속된 좌석에 따른 앉을 수 있는 방법은 정해져 있기 때문에, n차원 벡터에서 연속된 구간의 길이를 구하면 됩니다. 그리고 난 뒤에 미리 연속된 좌석의 방법의 수를 계산해놓은 배열을 참조하여 해당 숫자를 모두 곱하면 끝입니다. 아래는 풀이입니다.

n = int(input())
m = int(input())

# 분기 처리는 하는 이유는 n = 1이면 그냥 1이기 때문입니다.
# 하지만 n = 2 이 경우는 달라요. 그러면 방법의 수가 1일수도 있고 2일수도 있습니다. 그래서 분리하는 겁니다.
if n >= 2:
    # 미리 연속된 좌석에 의한 방법의 수를 기록해 놓습니다.
    # 이건 아무도 vip가 없다는 가정하에 n이 최대입니다.

    dp = [1 for _ in range(n + 1)]
    #  2번째는 무조건 2입니다.
    dp[2] = 2

    # dp 계산해줍시다.
    # 계차수열의 점화식입니다.
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    # 밑의 데이터는 vip에요. vip 데이터를 받고 아래와 같은 코드를 통해 구간을 구해줍니다.
    i = 1
    answer = []
    for _ in range(m):
        idx = int(input())
        answer.append(idx - i)
        i = idx + 1
    answer.append(n - i + 1)

    # 미리 만든 dp를 통해 계산해줍시다.
    res = 1
    for a in answer:
        res *= dp[a]
    print(res)
else:
    for _ in range(m):
        v = int(input())
    print(1)