[백준/BOJ] 1520번 : 내리막 길, 10942번 : 팰린드롬? (DP, 동적 계획법 중급)

​이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1520번 : '내리막 길', 10942번 : '팰린드롬?' 문제의 풀이 코드와 해설을 다루고 있습니다.

문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 DP(동적 계획법)의 활용에 대한 이해가 필요합니다.

 

 

1520번 : 내리막 길

 

숫자로 주어진 N×M의 map이 주어지고 (0, 0)에서 더 작은 수로만 이동하여 (N, M)까지 이동한다고 할 때, 몇 가지의 경로가 존재하는지를 찾는 문제입니다.

단순한 DFS로 해결이 가능해보이며, 여기에 DP를 활용하여 경로의 수를 기록하면서 풀이하면 되는 문제입니다.

 

 

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

int N, M;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int Map[MAX][MAX], dp[MAX][MAX];

int Search(int x, int y) {
    if(x == N-1 && y == M-1) return 1;
    if(dp[x][y] != -1) return dp[x][y];

    dp[x][y] = 0;
    for(int i=0; i<4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 0 && ny >= 0 && nx < N && ny < M && Map[nx][ny] < Map[x][y])
            dp[x][y] += Search(nx, ny);
    }
    return dp[x][y];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N >> M;

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) {
            cin >> Map[i][j];
            dp[i][j] = -1;
        }

    cout << Search(0, 0);
}

 

우선은 Map을 입력받고, 지나갔던 칸을 다시 지나가지 않도록 하기 위해 dp를 -1로 초기화해줍니다. (만약 지나갔다면 dp != -1일 것이고, 그러한 칸은 계산에 넣지 않도록 하기 위해서입니다.)

그 다음 DFS를 그대로 구현해주되, 경로의 수를 dp값에 저장해주면 됩니다.

물론 dp[i][j] = (i, j)에서 (N, M)까지 도달할 수 있는 내리막 경로의 수로 정의됩니다.

 

 

 

 

10942번 : 팰린드롬?

 

N개의 수가 입력되고, 구간 [S, E]에 해당하는 수열이 팰린드롬 수열인지의 여부를 출력하는 문제입니다.

N <= 10만이므로 배열에 작은 구간부터 팰린드롬 여부를 기록해가면서 풀이하는 전형적인 DP 문제입니다.

 

 

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

int arr[MAX], dp[MAX][MAX];

int solve(int i, int j) {
    if(dp[i][j] != -1) return dp[i][j];
    if(i == j) return 1;
    if(i+1 == j) return dp[i][j] = (arr[i] == arr[j]);
    if(arr[i] == arr[j] && solve(i+1, j-1) == 1) return dp[i][j] = 1;
    return dp[i][j] = 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];

    fill(&dp[0][0], &dp[MAX-1][MAX], -1);

    int M; cin >> M;
    while(M--) {
        int S, E; cin >> S >> E;
        cout << solve(S-1, E-1) << "\n";
    }
}

 

먼저 dp[i][j]를 "구간 [i, j]가 팰린드롬 수열인지의 여부"로 정의하는 것이 가장 편리하며, 초기 dp값은 -1로 초기화하여 1, 0과 구분되도록 합니다.

 

dp[i][j] != -1인 경우 : 이미 dp가 기록되었으므로 기록된 dp 값을 반환해줍니다. (return dp[i][j])

i == j인 경우 : 길이 1인 수열의 팰린드롬 여부이므로 이 경우는 true입니다. 또한 dp 문제이기 때문에 dp에 저장을 해주면서 그 값을 리턴해줍니다. (return dp[i][j] = 1)

i+1 == j인 경우 : 길이 2인 수열의 팰린드롬 여부이므로 arr[i]와 arr[j]가 같으면 true, 다르면 false입니다. 따라서 arr[i] == arr[j]를 리턴해주면 됩니다. 역시 dp에 저장해주면서 그 값을 리턴해줍니다.

 

나머지 경우 : 이제 점화식을 세워보면, arr[i] == arr[j]이면서, solve(i+1, j-1)이 true면 구간 [i, j]에 대한 수열도 팰린드롬 수열이라고 할 수 있습니다.

재귀적으로 리턴 값을 받아 풀이하도록 위의 코드와 같이 설계하면 쉽게 해결 가능합니다.