백준 1146번: 지그재그 서기 (C++)

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

1146번: 지그재그 서기

---

Level: Platinum V

Solved By: DP, Math

 

해당 포스트(https://jeongboclass.tistory.com/57)의 풀이를 참고하였습니다.

 

이 문제는 보면 Brute-Force 하게 풀기에는 N의 Max가 100이라 불가능합니다. 그래서 어떠한 패턴이 있는 건지 찾아보려 했지만 알 수는 없었습니다. DP로 풀어야 할 거 같은데 감은 오지 않고, 풀이를 참고해야 했습니다.

 

풀이의 생각과 저의 생각의 가장 큰 차이점은 '어떤 수인지 신경을 쓰냐 안 쓰냐'의 문제였습니다.

저는 순열을 구하면서 현재 수와 전 수의 크기를 비교하며 다음 수를 골라야 한다고 생각했습니다. 그 과정에서 '다음 수가 이전에 이미 골랐던 수인가?'를 고려해야 했기 때문에 풀이를 해내기 어려웠습니다.

 

그렇다고 하기엔 제 풀이도 O(N!)으로 예상되어 불가능하기 때문에 이건 아니라고 생각해서 특정 패턴이 있는지도 몇 개의 케이스를 보며 파악해보려 했지만 꽤 어려웠습니다.

 

참고한 포스트의 풀이는 DP이면서 Recursive Call로 풀어냈는데 특징은 이러했습니다.

현재 선택한 개수에서 왼쪽과 남아있는 수의 개수와 오른쪽에 남아있는 수의 개수는 몇 개인가

이 아이디어의 핵심을 잘 살렸다고 생각한 부분은 Recursive Call의 다음 단계로 넘어가는 반복문에서 잘 드러납니다.

if(dir == 0){ // 작은 수를 고르는 단계
    for(int i = l - 1; i >= 0; i--){
        ret = (ret + solve(idx + 1, i, r + (l - i - 1), 1) % MOD) % MOD;
            // 다음 recursive call의 단계에서는
            // 현재 서있는 학생의 수가 idx + 1이 되고,
            // 왼쪽에 남아있는 수는 i가 된다.
            // 오른쪽에 남아있는 수는 r + (l - i - 1)이 남게 되는데
            // (l - i - 1)에서 l - i는 왼쪽에서 위치를 골라 i로 이동했기 때문에
            // 오른쪽에는 r + (l - i)개가 남는 것이고, 거기다가 -1을 해준 이유는
            // 이동해왔기 때문에 더 이상의 중복은 허용하지 않으므로 -1을 해주었다.
            // 그리고 작은 수를 골랐기 때문에 dir parameter는 1을 할당한다.
   }
}
else{ // 큰 수를 고르는 단계
    for(int i = r - 1; i >= 0; i--){
        ret = (ret + solve(idx + 1, l + (r - i - 1), i , 0) % MOD) % MOD;
    }
}

작은 수를 고르는 단계에서 주석을 잘 봅시다. 풀이에서 반복문과 solve 함수의 Parameter를 보며 감탄했습니다.

작은 수를 고르는 단계에서도 여러 경우가 있습니다. 작은 수가 N개라면 N개의 모든 경우를 대입해봐야 하니까요.

반복문은 그 모든 경우를 탐색하고 있습니다. 그리고, solve 함수의 Parameter에서는 다음 사람 수는 idx + 1, 이제 왼쪽에 남아있는 사람의 수는 i, 오른쪽에 남아있는 사람의 수는 r + (l - i - 1), 그리고 다음 방향을 나타내는 1

 

오른쪽에 남아있는 사람의 수가 r + (l - i - 1)인 이유는 기존의 오른쪽에 있던 사람의 수 r과 위치를 이동하게 되며 오른쪽으로 위치하게 될 사람 l - i, 그리고 기존의 있던 위치를 뺀 -1로 정리됩니다. 이 -1이 전 좀 놀라웠습니다.

 

이 부분에서 문제의 핵심을 알아낼 수 있었습니다. '어떤 수인지는 상관없다. 어떤 수를 골랐을 때 왼쪽, 오른쪽에 남아있는 사람의 수가 중요하다. N명의 사람을 골라냈을 때, 왼쪽과 오른쪽에 남아있는 사람이 없다면 그게 가능한 케이스다.'

 

그리고, DP로 한 번에 답을 구하려니 더욱 풀이에 접근을 못 하지 않았나 싶습니다. 참고 포스팅에서는 1~N까지의 모든 탐색을 하되 그것이 다음 수는 작은 수인지 큰 수인지를 모두 탐색하여 가능한지 불가능한지를 탐색하여 모든 경우를 더했으니까요.

for(int i = 1; i <= N; i++){
    ans = (ans + solve(1, i - 1, N - i, 0) % MOD) % MOD;
    ans = (ans + solve(1, i - 1, N - i, 1) % MOD) % MOD;
}

 

나중에도 이런 문제를 한 번 더 만나보고 싶습니다. 이해하고 나니 정말 신기한 아이디어였네요.

#include <iostream>
#include <memory.h>
#define MAX 101
#define MOD 1000000
using namespace std;

int cache[MAX][MAX][MAX][2];
int N;

// idx : 현재 줄에 서있는 학생, dir : 현재 골라야하는 방향
// l : 왼쪽에 남아있는 수, r : 오른쪽에 남아있는 수
int solve(int idx, int l, int r, bool dir){
    if(cache[idx][l][r][dir] >= 0) return cache[idx][l][r][dir]; // 시간을 줄이기 위한 Memoization
    
    if(idx == N){
        // 종료 조건
        if(!l && !r) return cache[idx][l][r][dir] = 1; // 왼쪽, 오른쪽 더 이상 남은 수가 없다
        else return cache[idx][l][r][dir] = 0;
    }
    else{
        int ret = 0;
        
        // 반복문에서 i는 특정 index라 생각하지 않고,
        // 어떤 index를 골랐을 때, 남게되는 수라 생각한다.
        
        if(dir == 0){ // 작은 수를 고르는 단계
            for(int i = l - 1; i >= 0; i--){
                ret = (ret + solve(idx + 1, i, r + (l - i - 1), 1) % MOD) % MOD;
                // 다음 recursive call의 단계에서는
                // 현재 서있는 학생의 수가 idx + 1이 되고,
                // 왼쪽에 남아있는 수는 i가 된다.
                // 오른쪽에 남아있는 수는 r + (l - i - 1)이 남게 되는데
                // (l - i - 1)에서 l - i는 왼쪽에서 위치를 골라 i로 이동했기 때문에
                // 오른쪽에는 r + (l - i)개가 남는 것이고, 거기다가 -1을 해준 이유는
                // 이동해왔기 때문에 더 이상의 중복은 허용하지 않으므로 -1을 해주었다.
                // 그리고 작은 수를 골랐기 때문에 dir parameter는 1을 할당한다.
            }
        }
        else{ // 큰 수를 고르는 단계
            for(int i = r - 1; i >= 0; i--){
                ret = (ret + solve(idx + 1, l + (r - i - 1), i , 0) % MOD) % MOD;
            }
        }
        
        return cache[idx][l][r][dir] = ret;
    }
}

int main(){
    cin >> N;
    
    if(N == 1) cout << 1;
    else{
        memset(cache, -1, sizeof(cache));
        int ans = 0;
        
        for(int i = 1; i <= N; i++){
            ans = (ans + solve(1, i - 1, N - i, 0) % MOD) % MOD;
            ans = (ans + solve(1, i - 1, N - i, 1) % MOD) % MOD;
        }
        
        cout << ans;
    }
    
    return 0;
}