[백준 17069번] [동적 계획법] 파이프 옮기기 2

Approach

특정한 조건에 의해서 경향성이 결정지어지는 것을 보고 점화식을 통해 방법의 수를 찾을 수 있을 것이라는 느낌을 받을 수 있다.

다만 (N, N)으로 뻗어나가는 방향으로는 판단하기가 어려운데, 왜냐하면 뻗어나가는 것은 이전 파이프의 상태로 가로/세로/대각 여부에 따라 달라지기 때문이다.

 

따라서 DP를 해당 좌표를 기준으로 들어오는 것을 기준으로 점화식을 세워주면 된다.

 

dp[i][j][0~3] : (i, j)에서 0~3번의 방향으로 들어오는 경우의 수 (단, 0은 대각선, 1은 세로, 2는 가로 방향)

 

추가적으로 들어오는 것을 기준으로 판단하고 있는 상황이므로, Top-down 방식을 활용하면 좋다는 것을 알 수 있다.

(Bottom-up 방식은 다음 블로그를 참고하도록 하자. https://rebas.kr/838)

BOJ 17069 · 파이프 옮기기 2

 

Top-down일 때의 점화식은 다음과 같다.

 

dp[i][j][0] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2] ( for i > 1, j > 1 & (i, j) and (i - 1, j), (i, j - 1) is not a wall)

                  = 0 (Else cases)

 

dp[i][j][1] = dp[i - 1][j][0] + dp[i - 1][j][1] ( for i > 1, j >= 1 & (i, j) is not wall)

                 = 0 (Else cases)

 

dp[i][j][2] = dp[i][j - 1][0] + dp[i][j - 1][1] ( for i >= 1, j > 1 & (i, j) is not wall)

                  = 0 (Else cases)

 

추가적으로 벽인지 확인하는 함수를 따로 만들어서, index 범위를 넘어서거나 벽인 경우에 동일한 값을 출력하게끔하면

딱히 위 점화식처럼 케이스를 많이 찢지 않아도 된다.

 

전체 문제를 풀기 위해서 부분 문제로 찢어야 한다는 관점에서 개인적으로는 Top-down 방식이 더 직관적인 풀이 방법 같다.

해당 좌표에 들어오는 파이프의 방향이 중요하다는 것을 인식해주면 dp 인자를 3개 잡아야한다는 사실은 쉽게 관찰할 수 있을 것이다. DP문제에서 가장 중요한 지점은 최소한의 인자를 활용하여 점화식을 구현하는 것이다. 이 문제의 경우는 좌표 값 2개, 파이프의 방향 1개이므로 총 3개인 것이다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int state[33][33];
int n;
long long dp[33][33][3];

int state_value(int x, int y){
    if(x < 1 || y < 1 || x > n || y > n) return 1;
    else return state[x][y];
}

long long solve(int x, int y, int index){
    if(x < 1 || y < 1 || x > n || y > n) return 0;
    
    if(dp[x][y][index] != -1) return dp[x][y][index];
    if(state_value(x, y)) return dp[x][y][index] = 0;

    //First check (대각)
    if(index == 0){
        if(state_value(x - 1, y) == 0 && state_value(x, y - 1) == 0){
            return dp[x][y][index] = solve(x - 1, y - 1, 0) + solve(x - 1, y - 1, 1) + solve(x - 1, y - 1, 2);
        }    
        else return dp[x][y][index] = 0; 
    }
    // Second check (vertical)
    else if(index == 1){
        return dp[x][y][index] = solve(x - 1, y, 0) + solve(x - 1, y, 1);
    }
    // Third check (horizontal)
    else{
        return dp[x][y][index] = solve(x, y - 1, 0) + solve(x, y - 1, 2);
    }
}

int main(void){
    fastio;
    fill(&dp[0][0][0], &dp[32][33][3], -1);
    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> state[i][j];
        }
    }
    dp[1][1][0] = 0;
    dp[1][1][1] = 0;
    dp[1][1][2] = 0;
    dp[1][2][2] = 1;
    
    cout << solve(n, n, 0) + solve(n , n, 1) + solve(n, n, 2) << "\n";
    return 0;
}