알고리즘 문제해결 전략 Chapter 08 - TRIPATHCNT (C++)

예제: 삼각형 위의 최대 경로 개수 세기

문제
9
5 7
1 3 2
3 5 5 6
위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다.

이 때 숫자의 합이 가장 큰 경로는 하나가 아니라 여러 개일 수 있습니다. 예를 들어 위 삼각형에서는 {9, 7, 2, 6}과 {9, 7, 3, 5}의 합이 모두 최대인 24이고, {9, 7, 3, 5}는 두 번 등장하거든요.

삼각형이 주어질 때 최대 경로의 수를 세는 프로그램을 작성하세요.

입력
입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 삼각형의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에는 각 1개~n개의 숫자로 삼각형 각 가로줄에 있는 숫자가 왼쪽부터 주어집니다. 각 숫자는 1 이상 100000 이하의 자연수입니다.

출력
각 테스트 케이스마다 한 줄에 최대 경로의 수를 출력합니다.
경로의 수는 230 이하라고 가정해도 좋습니다.

예제 입력
2
4
1
1 1
1 1 1
1 1 1 1
4
9
5 7
1 3 2
3 5 5 6

예제 출력
8
3

풀이

이 예제는 두 가지의 동적 계획법 문제가 결합되어있다.
1. 삼각형 위의 최대 경로 값 구하기
2. 삼각형 위의 최대 경로를 따라 개수 구하기

하나씩 살펴보도록 하자.

1. 삼각형 위의 최대 경로 값 구하기

표현이 애매할 수 있는데, 이를 설명하기 위해 예시 문제를 살펴보자.
9
5 7
1 3 2
3 5 5 6

문제를 작은 단위로 쪼개면, 아래와 같은 삼각형을 얻을 수 있다.
1
3 5
여기서 최대 경로 값을 어떻게 구할까?

첫 번째 방법은, 위에서 부터 하나씩 더해 구할 수 있다.
1
4 6
따라서, 4와 6중 최대 경로 값은 6이다.

그러나 반대로, 아래에서부터 더할 수 있다.
3과 5중 큰 값인 5을 위에 더해주면
6
3 5
이므로, 답은 6이다.

이를 식으로 나타내면,
(y, x) = max((y + 1, x), (y + 1, x + 1))
과 같이 나타낼 수 있다.

그러므로, 이 식을 적용하여 아래에서부터 위 예제를 풀어보면
9
5 7
1 3 2
3 5 5 6
의 풀이는
24
13 15
06 08 08
03 05 05 06
이므로, 최대 경로 값은 24 인 것이다.(간격을 맞추기 위해 0을 넣었다..)

큰 문제를 작은 문제로 쪼갤 수 있고, 삼각형의 맨 아래에서부터 위로 더해 올라가는 형식이므로, 다음과 같이 재귀 함수로 구현할 수 있다.

int triPath(int y, int x) {
    int& res = cache[y][x];
    if (res != -1) return res;

    if (y == N - 1) {
        return res = map[y][x];
    }

    res = max(map[y][x] + triPath(y + 1, x), map[y][x] + triPath(y + 1, x + 1));

    return res;
}

2. 삼각형 위의 최대 경로를 따라 개수 구하기

1
1 1
1 1 1
1 1 1 1
이런 삼각형이 있다고 하자. 최대 경로 값은 쉽게 4인것을 알 수 있다.
그러나, 4를 만들 수 있는 경로의 개수는 어떻게 구할 수 있을까?
위 문제야 쉽게 8개인 것을 알 수 있지만, 삼각형의 높이가 늘어날수록 계산하기가 어렵다.

위에서 삼각형의 최대 경로 값을 계산한 삼각형을 보자.
9
5 7
1 3 2
3 5 5 6
을 푼 결과는
24
13 15
06 08 08
03 05 05 06
이다.

이 또한 작은 문제로 나누어보자.
3
5 5
삼각형의 최대 경로를 구한 삼각형은
8
5 5
가 된다.
이 삼각형의 최대 경로 값 8을 구하기 위한 경로의 개수는? 볼것도 없이 2개이다.

다른 작은 문제를 보자.
2
5 6
이 삼각형의 최대 경로를 구한 삼각형은
8
5 6
이다.
최대 경로 값 8을 구하기 위한 경로의 개수는 1개이다.

즉, (y, x) 지점의 최대 경로의 개수는
(y + 1, x) 지점의 최대 경로의 개수를 a, (y + 1, x + 1) 지점의 최대 경로의 개수를 b라고 할 때,

if (y + 1, x) == (y + 1, x + 1) then (y, x) 지점의 최대 경로의 개수 = a + b
else if (y + 1, x) > (y + 1, x + 1) then (y, x) 지점의 최대 경로의 개수 = a
else if (y + 1, x) < (y + 1, x + 1) then (y, x) 지점의 최대 경로의 개수 = b

위와 같은 식을 얻을 수 있다.

이 또한 작은 문제로 나눌 수 있고, 아래에서 위로 더해가는 식이므로, 재귀함수로 구현할 수 있다.

int triPathCnt(int y, int x) {
    int& res = cache2[y][x];
    if (res != -1) return res;

    if (y == N - 1) {
        return 1;
    }

    int pre = cache[y + 1][x];
    int next = cache[y + 1][x + 1];
    int n1 = triPathCnt(y + 1, x);
    int n2 = triPathCnt(y + 1, x + 1);
    if (pre == next) {
        res = n1 + n2;
    }
    else if (pre > next) {
        res = n1;
    }
    else {
        res = n2;
    }

    return res;
}

위의 triPath() 함수와 상당히 비슷한 형태인 것을 볼 수 있다.

필자는 처음에

int pre = triPathCnt(y + 1, x);
int next = triPathCnt(y + 1, x + 1);
res = (cache[y + 1][x] == cache[y + 1][x + 1] ? pre + next : max(pre, next));

와 같이 풀었다가 틀렸는데, (y, x) 지점의 값은 이렇게 되면 cache[y + 1][x] > cache[y + 1][x + 1] 인 경우에 next가 더해질 수 있으므로, 오답이 된다.

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int N;
int map[100][100];
int cache[100][100];
int cache2[100][100];

int triPath(int y, int x) {
	int& res = cache[y][x];
	if (res != -1) return res;

	if (y == N - 1) {
		return res = map[y][x];
	}

	res = max(map[y][x] + triPath(y + 1, x), map[y][x] + triPath(y + 1, x + 1));

	return res;
}

int triPathCnt(int y, int x) {
	int& res = cache2[y][x];
	if (res != -1) return res;

	if (y == N - 1) {
		return 1;
	}

	int pre = cache[y + 1][x];
	int next = cache[y + 1][x + 1];
	int n1 = triPathCnt(y + 1, x);
	int n2 = triPathCnt(y + 1, x + 1);
	if (pre == next) {
		res = n1 + n2;
	}
	else if (pre > next) {
		res = n1;
	}
	else {
		res = n2;
	}

	return res;
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		memset(cache, -1, sizeof(cache));
		memset(cache2, -1, sizeof(cache2));
		
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= i; j++) {
				cin >> map[i][j];
			}
		}

		triPath(0, 0);
		cout << triPathCnt(0, 0) << endl;
	}

	return 0;
}

풀이 후기

풀이를 보면, 같은 식이라도

if(path2(y + 1, x + 1) >= path2(y + 1, x)) ret += count(y + 1, x + 1);
if(path2(y + 1, x + 1) <= path2(y + 1, x)) ret += count(y + 1, x);

등으로 표현했던데 상당히 깔끔한 것을 알 수 있다.

그리고 필자는 main함수에서 최대 경로 값을 구하는 함수와 최대 경로 값의 개수를 구하는 함수를 각각 호출했는데, 최대 경로 값의 개수를 구하는 함수 내부에서 최대 경로 값을 구하는 함수를 호출하여, 좀 더 함수를 보기좋게 만들 수 있지 않을까 싶다.

알고리즘 문제해결전략 2회차 돌때 다양한 방법으로 시도해봐야겠다.