[Python/C++] 백준 18790 - N의 배수 (1)

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

풀이

1번째 시도(시간초과/메모리초과)

일단, 주어진 리스트에서 각 수가 몇 번 등장하는지를 센다.

가장 먼저 떠오른 건 DP. 대충 N의 범위가 500이니까 인자를 3개 잡는 재귀함수 형식으로 짜자.

인자는 다음과 같다.

 

dp[현재 처리하는 수][현재까지 쓴 수의 개수][현재 나머지]

 

마지막에 dp[N-1][N][0]을 불러서, 정답에 도달할 수 있는지 본다. dp 함수의 리턴값은 [현재 처리하는 수]가 몇 개 쓰였는지이다.

이 값을 이용해서 역추적할 수 있다.

 

랜덤하게 생성해낸 데이터에 대해서 잘 돌아가였고, 자신만만하게 제출하였으나,,,,

 

 

2번째 시도(시간초과/메모리초과)

dp 인자를 바꿔볼까?

주어진 리스트에서 각 수의 등장 횟수를 카운트하는 작업을 빼고,

 

dp[리스트에서 idx번째까지 수를 써서][현재까지 쓴 수의 개수][나머지] (나중에 알았는데 이게 에디토리얼에 설명된 풀이이다....?)

 

마찬가지로 마지막에 dp[2N-2][N][0]을 부르는 재귀함수 형식으로 짰다.

그런데 이 시도 방식이 1번째 시도 방식보다 2배 더 루프를 도는 거 아닌가?

 

 

여기서 약간 멘붕이 왔다. 혹시 dp의 인자가 3개가 아닌가?

 

3번째 시도(AC)

문득 이런 생각이 났다. 'idx번째 수까지 처리' 인자를 없애고, dp 테이블을 2차원으로 만들 수 있지 않을까? 근데 그러면 N 이 500정도로 작을리가 없는데?

여기서 깨달음을 얻었다.

 

아, dp테이블이 2차원이라 하더라도 O(N^3)일 수 있구나!

 

dp[현재까지 쓴 수의 개수][나머지]

 

0개 써서 나머지가 0, 즉 (0, 0)부터 스택에 집어넣는다. 그러니까 이제부터 탐색할 칸들을 스택에 집어넣겠다 이거다.

주어진 리스트들의 각 원소에 대해서, 스택에 들어가있는 칸 (i, j)들을 갱신 시도를 한다.

만약 dp[i+1][(j+arr[idx])%N]에 아무 값도 들어가있지 않다면, dp의 값을 현재 원소의 인덱스 값으로 한다.

그러면 나중에 역추적할 때 i+1번째로 사용한 값이 어떤 값인지 알 수 있다.

 

여기서 아무 값도 들어가있지 않을 때, 즉 이미 정해진 값을 이미 안 건드는 이유는,

해당 칸을 거쳐서 다른 칸으로 넘어가야하는데 만약 이 '거치는 칸'의 값이 변경되면 역추적이 불가능하기 때문이다.

 

이해를 돕기 위해, 문제에 주어진 예제의 경우 dp 테이블이 어떻게 채워지는지 적어놓겠다.

 

 

파이썬

import sys

N = int(input())
arr = list(map(int, input().split()))
dp = [[None]*N for _ in range(N+1)]
for i in range(N):
    dp[0][i] = -1

stack = [(0, 0)]
for idx in range(2*N-1):
    tmp = []
    for i, j in stack:
        if dp[i+1][(j+arr[idx])%N] is None:
            dp[i+1][(j+arr[idx])%N] = idx
            if i+1 <= N-1:
                tmp.append((i+1, (j+arr[idx])%N))
    stack += tmp

if dp[N][0] is None:
    print(-1)
    sys.exit()

now = 0
for i in range(N, 0, -1):
    ans = arr[dp[i][now]]
    print(ans, end = ' ')
    now = (now - ans) % N

 

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N; cin >> N;
    int arr[2*N-1];
    for (int i = 0; i < 2*N-1; i++) {
        cin >> arr[i];
    }

    vector<vector<int>> dp(N + 1, vector<int>(N, -2));
    for (int i = 0; i < N; i++) {
        dp[0][i] = -1;
    }
    
    vector<pair<int, int>> stack;
    stack.emplace_back(0, 0);

    for (int idx = 0; idx < 2*N-1; idx++) {
        vector<pair<int, int>> tmp;

        for (auto [i, j] : stack) {
            int ni = i + 1;
            int nj = (j + arr[idx]) % N;

            if (ni <= N && dp[ni][nj] == -2) {
                dp[ni][nj] = idx;
                if (ni <= N - 1) {
                    tmp.emplace_back(ni, nj);
                }
            }
        }

        stack.insert(stack.end(), tmp.begin(), tmp.end());
    }

    int now = 0;
    for (int i = N; i > 0; i--) {
        int ans = arr[dp[i][now]];
        cout << ans << ' ';
        now = (now - ans + N) % N;
    }


}

 

다른 분들의 코드를 보니까 3인자 dp를 구현하기 위해 비트마스킹, 비트셋 등 다양한 최적화 기법들을 이용하셨는데 파이썬으로는 감히 못하겠다.

 

 

다음 편 예고

 

그런데 여기서 레전드 떡밥이 하나 있다.

그 어떠한 케이스를 짜도 절대로 -1, 즉 불가능한 경우가 나오지 않는다는 것이다????

 

여기에 대해서는 다음 시간에.....무려 D2짜리 18791 N의 배수 (2)를 도전해보며 적어보겠다.