[Week 2] TRIPATHCNT self review - Choi-mina

[Choi-mina]

TRIPATHCNT self review

• 파일명: STU/STRIPATHCNT/Choi-mina.cpp
• 수행시간: 12ms

1. 고민 과정

최대경로를 구하고 최대경로의 개수도 구해야 했기 때문에 어떻게 함수를 만들어야 할지 고민을 했습니다.

2. 풀이 아이디어

전에 DP는 재귀함수를 이용하면 조금 더 쉽게 풀 수 있다는 이야기를 들었던 것 같아서 재귀함수를 이용했습니다.
가려고 하는 방향을 재귀함수를 사용해 최대 경로를 구하도록 했습니다.

3. 작성한 코드와 설명

int path(int x, int y) {
	if (x == n - 1) return tri[x][y];
	int& maxpath = cache_max[x][y];
	if (maxpath != -1) return maxpath;
	maxpath = tri[x][y] + max(path(x + 1, y), path(x + 1, y + 1));
	return maxpath;
}

path() 함수는 최대경로를 구하는 함수입니다.
재귀함수를 이용해 tri[x][y] 바로 아래있는 숫자 (x+1, y)와 오른쪽 아래인 숫자 (x+1, y+1) 중 최댓값을 원래 위에 있던 숫자인 tri[x][y]와 더해주었습니다.

int path_count(int x, int y) {
	if (x == n - 1) return 1;
	int& pathcount = cache_path[x][y];
	if (pathcount != -1) return pathcount;
	pathcount = 0;
	if (path(x + 1, y + 1) >= path(x + 1, y)) pathcount += path_count(x + 1, y + 1);
	if (path(x + 1, y + 1) <= path(x + 1, y)) pathcount += path_count(x + 1, y);
	return pathcount;
}

path_count() 함수는 최대경로의 개수를 구하는 함수입니다.
path() 함수를 이용해 최대 경로를 구하고 더 큰 값을 pathcount 변수에 넣어 반환을 하였습니다.

int main() {
	ios_base::sync_with_stdio(0);
	cin >> c;
	for (int i = 0; i < c; i++) {
		memset(cache_max, -1, sizeof(cache_max));
		memset(cache_path, -1, sizeof(cache_path));

		cin >> n;
		for (int j = 0; j < n; j++) {
			for (int k = 0; k <= j; k++) {
				cin >> tri[j][k];
			}
		}
		cout << path_count(0, 0) << endl;
	}
	return 0;
}

메인함수에는 memset함수를 사용해 메모리의 값을 -1로 초기화를 해주었고 입력과 결과값 출력을 할 수 있도록 코드를 짜주었습니다.