백준 1904번: 01타일 (S3) - Python 풀이

문제 설명

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

요약) '00'과 '1'을 사용해서 길이가 N인 2진 수열을 만들어야 합니다. 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력하면 됩니다. 입력 N은 1 이상, 1,000,000 이하로 주어집니다.

예제 입력 1

4

예제 출력 1

5

-> 00과 1을 이어붙여 만들 수 있는 2진 수열 중에 크기가 4인 것은 1001, 1100, 0011, 0000, 1111 로 총 5개입니다.

풀이 과정

DP는 하나의 문제를 여러 개의 중복되는 문제로 나누는 Overlapping subproblems와, 작은 문제의 답들을 재사용하여 큰 문제의 정답을 구할 수 있다는 Optimal substructure의 조건을 만족해야 합니다.

해당 문제의 경우, N은 자릿수만을 결정하고, 00과 1을 이어붙여 결과를 만드는 문제입니다. 그렇기 때문에 N의 결과가 이전 결과에 영향을 받는다고 생각했습니다. 그래서 규칙을 구하고자 N이 1일 때부터 5일 때까지 출력값을 구해 보았습니다.

N=1, 1 -> 1개
N=2, 11, 00 -> 2개
N=3, 100, 001, 100 -> 3개
N=4, 1100, 1100, 0011, 1111, 0000 -> 5개
N=5, 11111, 00111, 11001, 10011, 00001, 11100, 10000, 00100 -> 8개
...

이를 통해 N일 때의 결과값은 (N-1일 때의 결과값) + (N-2일 때의 결과값) 과 같다는 규칙을 구할 수 있었습니다. 작은 문제로 쪼개지고, 이 작은 문제의 답을 통해 큰 문제의 답을 구할 수 있기에 DP임을 확신했습니다. 그래서 저는 작은 문제의 답을 저장해두는 memoization 기법을 사용했습니다.

이걸 알았음에도 바로 답을 맞히지는 못 했는데 (메모리 초과가 발생했습니다!), 이 문제의 또다른 포인트가 있었기 때문입니다.

위의 문제 설명에서 적어둔 것처럼 이 문제는, 바로 '만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지'를 출력해야 하는 문제입니다. 즉 (N-1일 때의 결과값) + (N-2일 때의 결과값)이 15746이 된다면 바로 0을 출력해야 하는 것입니다. 15747이면 1, 15748이면 2, 15749면 3, ... 즉 15746을 기준으로 답이 반복된다는 것입니다.

저장해야 하는 값이 커질수록 메모리를 더 많이 쓰게 됩니다. 어차피 이 문제에서 출력으로 나오는 가장 큰 수는 15745일 것이니, 그것보다 더 큰 수를 memo에 저장해둘 필요가 없겠죠. 그래서 (N-1일 때의 결과값) + (N-2일 때의 결과값) 이 15746보다 같거나 큰 경우에는 15746으로 나눈 나머지를 memo에 저장하는 식으로 구현했고, 답을 맞힐 수 있었습니다.

N = int(input())

# N이 1일 때에도 아래의 코드가 문제 없이 돌아가도록 하기 위해 N+2로 크기를 잡았다.
memo = [0] * (N+2)
memo[1], memo[2] = 1, 2 # 초기값 설정

def calculate(N):
    # 이미 알고 있는 값들은 바로 memo에서 리턴
    if N == 1 or N == 2:
        return memo[N]
    # 아닌 것들은 for문을 통해 구한다
    for i in range(3, N+1):
        tmp = memo[i-1] + memo[i-2]
        # 작은 문제의 합이 15746보다 크거나 같으면
        if tmp >= 15746:
            # memo에 그 나머지를 저장한다
            memo[i] = tmp % 15746
        # 작은 문제의 합이 15746보다 작으면
        else:
            # 나머지가 아닌 합을 그대로 저장한다
            memo[i] = tmp
    return memo[N]

print(calculate(N))

이번 스터디 때는 접근법까지 꼭 잘 발표할 수 있기를...!