백준24418 알고리즘 수업-행렬 경로 문제1 C/C++

알고리즘 수업 - 행렬 경로 문제 1 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

142

101

81

74.312%

문제

오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

양의 정수로 이루어진 n × n 행렬 m이 주어진다. 행렬의 왼쪽 위에서 시작해 한 칸씩 이동해 오른쪽 아래까지 도달한다. 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합이다. 이동 규칙은 다음과 같다.

• 오른쪽이나 아래쪽으로만 이동할 수 있다.
• 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.

행렬의 원소 (1, 1)에서 (n, n)으로 이동하는 모든 경로의 점수 중 가장 높은 점수를 구하는 행렬 경로 문제 의사코드는 아래와 같다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 행렬의 크기 n과 행렬 m이 주어진 경우 코드1 코드2 실행 횟수를 출력하자.

행렬 경로 문제 재귀호출 의사 코드는 다음과 같다.

matrix_path(m[][], n) {  # (1, 1)에서 (n, n)에 이르는 최고 점수를 구한다.
    return matrix_path_rec(m, n, n);
}
matrix_path_rec(m[][], i, j) {  # (1, 1)에서 (i, j)에 이르는 최고 점수를 구한다.
    if (i == 0 or j == 0) then
        return 0; # 코드1
    else
        return (mij + (max(matrix_path(m, i-1, j), matrix_path(m, i, j-1))));
}

행렬 경로 문제 동적 프로그래밍 의사 코드는 다음과 같다.

matrix_path(m[][], n) {  # (1, 1)에서 (n, n)에 이르는 최고 점수를 구한다.
    for i <- 0 to n
        d[i, 0] <- 0;
    for j <- 1 to n
        d[0, j] <- 0;
    for i <- 1 to n
        for j <- 1 to n
            d[i, j] <- mij + max(d[i - 1, j], d[i, j - 1]);  # 코드2
    return d[n, n];
}

입력

첫째 줄에 행렬의 크기 n(5 ≤ n ≤ 15)이 주어진다.

그 다음 n개의 줄에는 각 줄마다 행렬의 각 행을 나타내는 n개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 1 이상 100,000 이하이다.

출력

코드1 코드2 실행 횟수를 한 줄에 출력한다.

예제 입력 1 복사

5
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

예제 출력 1 복사

252 25

#include <iostream>

using namespace std;


int arr1[16][16]={0};
int arr2[16][16]={0};
int cnt1=0, cnt2 = 0;

int max(int a, int b)
{
    if (a >= b)
        return a;
    else
        return b;
}

int matrix_path(int i, int j)
{
    cnt1++;
    if (i == 1 && j == 1)
        return arr1[1][1];
    else if (i == 1)
        return arr1[1][j] + matrix_path(1, j - 1);
    else if (j == 1)
        return arr1[i][1] + matrix_path(i - 1, 1);
    else
        return arr1[i][j] + (max(matrix_path(i - 1, j), matrix_path(i, j - 1)));
}

int matrix_path_dp(int n)
{
    arr2[1][1] = arr1[1][1];
    for (int i = 2; i <= n; i++)
    {
        arr2[i][1] = arr1[i][1] + arr2[i - 1][1];
        cnt2++;
    }
    for (int j = 2; j <= n; j++)
    {
        arr2[1][j] = arr1[1][j] + arr2[1][j - 1];
        cnt2++;
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 2; j <= n; j++)
        {
            arr2[i][j] = arr1[i][j] + max(arr2[i - 1][j], arr2[i][j - 1]);
            cnt2++;
        }
    }
    return arr2[n][n];
}

int main(void)
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cin >> arr1[i][j];
    }
    matrix_path(n, n);
    matrix_path_dp(n);
    printf("%d ",cnt1+1);
    printf("%d", cnt2+1);

    return 0;
}

 

 

수도코드를 그대로 따라하다가 잘 안돼서 '쉽게 배우는 알고리즘'이란 책의 수도코드를 참고했다.

 

matrix_path(m[][], n) {  # (1, 1)에서 (n, n)에 이르는 최고 점수를 구한다.
    return matrix_path_rec(m, n, n);
}
matrix_path_rec(m[][], i, j) {  # (1, 1)에서 (i, j)에 이르는 최고 점수를 구한다.
    if (i == 0 or j == 0) then
        return 0; # 코드1
    else
        return (mij + (max(matrix_path(m, i-1, j), matrix_path(m, i, j-1))));
}

 

이 백준 수도코드에서는 matrix_path에 전달하는 인자가 2개인데, return 부분에 매개변수가 3개있어서 저 수도코드로는 안풀린다. 그래서 책의 걸로 했다.