[Week 2] TRIPATHCNT self review - Yunhyunjo

[Yunhyunjo]

TRIPATHCNT self review

• 파일명: STU/TRIPATHCNT/Yunhyunjo.cpp
• 수행시간: 12ms

1. 고민 과정

처음에 단순히 최대합만 구하는 것으로 문제를 잘못 보고 풀었다가 경로의 수를 구하는 문제인 것을 보고 다시 코드를 작성했습니다.
최대합을 저장하는 배열과 경로의 수를 저장하는 배열을 각각 만들어 풀면 된다고 생각하였습니다.

2. 풀이 아이디어

경로는 바로 아래 혹은 오른쪽 아래로만 가는 것이기 때문에 for문을 돌면서 둘 중 더 큰 값을 저장하는 방식으로 구현하였습니다.
또 경우의 수는 첫 번째가 클 때, 두 번째가 클 때, 같을 때 이 세 가지 경우의 수로 나누어 경로 수를 저장해 주었습니다.

3. 작성한 코드와 설명

vector <vector <int>> v(n+1, vector <int> (n+1, 0));
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= i; j++) {
		cin >> v[i][j];
	}
}

먼저 v에 삼각형을 입력해주었습니다.
합이나 경로를 계산할 때 배열의 범위를 벗어날 수 있기 때문에 좀 더 편하게 계산하기 위해 크기는 n +1로 해주고 0으로 초기화 시킨 후 입력을 받았습니다.

vector <vector <int>> dp(n+1, vector <int>(n+1, 0));
vector <vector <int>> dp2(n + 1, vector <int>(n + 1, 0));
dp[1][1] = v[1][1];
dp2 [1][1] = 1;
for (int i = 2; i <= n; i++) {
	for (int j = 1; j <= i; j++) {
		if (v[i][j] + dp[i - 1][j] > v[i][j] + dp[i - 1][j - 1]) {
			dp[i][j] = v[i][j] + dp[i - 1][j];
			dp2[i][j] = dp2[i - 1][j];
		}
		else if (v[i][j] + dp[i - 1][j] == v[i][j] + dp[i - 1][j - 1]) {
			dp[i][j] = v[i][j] + dp[i - 1][j];
			dp2[i][j] = dp2[i - 1][j] + dp2[i - 1][j - 1];
		}
		else {
			dp[i][j] = v[i][j] + dp[i - 1][j - 1];
			dp2[i][j] = dp2[i - 1][j - 1];
		}
	}
}

그 다음 합을 저장하는 배열 dp와 경로의 수를 저장하는 배열 dp2를 선언해 주고 v와 같은 이유로 n + 1의 크기로 선언해 주었습니다.
[1, 1] 에 값을 미리 넣어주고 2행부터 돌면서 dp에는 더 큰 합을 저장하고 dp2에는 경로의 합 들을 저장해 주었습니다.

int max = 0, cnt = 0;

for (int i = 1; i <= n; i++) {
	if (max < dp[n][i]) {
		max = dp[n][i];
		cnt = dp2[n][i];
	}
	else if (max == dp[n][i]) cnt += dp2[n][i];
}

cout << cnt << "\n";

마지막으로 최대 경로의 수를 구하기 위해 맨 마지막 행만을 탐색하면서 가장 큰 값을 찾고 경로가 몇 개가 있는지를 구해주었습니다.