[Week 2] TRIPATHCNT self review - Queue-ri

TRIPATHCNT self review

파일명: STU/TRIPATHCNT/Queue-ri.cpp
수행시간: 12ms

1. 고민 과정

최대합과 더불어 최대합이 되는 경로의 수까지 세어야 하는 문제입니다.

sum 과 count 용 배열 각각을 하나로 붙여서 3차원으로 선언할까 했다가, 가독성을 위해 2차원짜리 2개로 선언하기로 했습니다.

또한 base case를 레벨 N에서 단순히 0을 리턴하는 것으로 처리하려다가, 그러면 경로의 개수에서 오답이 나온다는 사실을 깨닫고 도중에 수정했습니다.

2. 풀이 아이디어

ppt의 풀이 가이드에 맞추어 재귀함수의 리턴값은 각 지점의 최대합이라고 정의합니다.

A
B C

A에서 호출한 B와 C의 리턴값이 동일하면 -> 최대합의 경로 수는 B와 C에서 계산된 경로 수의 합
B의 리턴값 < C의 리턴값이라면 -> 최대합의 경로 수는 C에서 계산된 경로의 수
B의 리턴값 > C의 리턴값이라면 -> 최대합의 경로 수는 B에서 계산된 경로의 수 입니다.

C++은 파이썬처럼 multi variable return이 안되기 때문에 경로 수는 count 배열의 캐시를 사용했습니다.

3. 작성한 코드와 설명

✨ 재귀함수

if (y == N - 1) {
	c_cache = 1;
	return tri[y][x];
}

삼각형의 단말노드에 도착했을 시 경로의 수를 세기 위해 1을 반환해주고, 합을 구하기 위해 현 지점의 숫자 값을 리턴합니다.

if (s_cache) return s_cache;

해당 지점의 최대합이 이미 캐싱되어있으면 캐시를 리턴합니다. 이 문제는 캐싱된 상태가 0값일 수는 없기 때문에 조건문 판별로 s_cache 값을 그대로 사용할 수 있습니다.

int a = find_path(y + 1, x);
int b = find_path(y + 1, x + 1);

if (a < b) c_cache = c[y + 1][x + 1];
else if (a > b) c_cache = c[y + 1][x];
else c_cache = c[y + 1][x] + c[y + 1][x + 1];

return s_cache = max(a, b) + tri[y][x];

2. 풀이 아이디어 파트의 내용을 그대로 구현했습니다. s_cache 할당은 마지막 리턴문 한줄로 간결하게 만들었습니다.

✨ main 함수

Advanced-Algorithm-Study/STU/TRIPATHCNT/Queue-ri.cpp

Lines 30 to 43 in a5d7dc8

    
           int main() { 
        
           	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); 
        
           	int TC; cin >> TC; 
        
           	while (TC--) { 
        
           		cin >> N; 
        
           		rep(i, 0, N) 
        
           			rep(j, 0, i+1) 
        
           				cin >> tri[i][j]; 
        
           		memset(s, 0, sizeof(s)); 
        
           		find_path(0, 0); 
        
           		cout << c[0][0] << endl; 
        
           	} 
        
           }

memset은 조건문에 사용되는 sum 배열만 해주었으며, 인덱스는 0에서 시작했습니다.

	int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int TC; cin >> TC;
	while (TC--) {
	cin >> N;
	rep(i, 0, N)
	rep(j, 0, i+1)
	cin >> tri[i][j];

	memset(s, 0, sizeof(s));
	find_path(0, 0);
	cout << c[0][0] << endl;
	}
	}