[Week 4] TRIPATHCNT self review - Scaachan

[Queue-ri]

TRIPATHCNT self review

• 파일명: TRIPATHCNT/Scaachan.cpp
• 수행시간: 16ms

1. 문제 해결 과정

TRIANGLEPATH 문제는 단순히 크기 비교만 하면 되니 간단했는데,

이 문제는 가장 큰 sum도 알아야 하고 해당 sum이 몇 개 있는지 카운팅도 해야 하기 때문에 생각이 더 필요했습니다.

함수의 반환은 기본적으로 하나만 가능한데, 이를 struct/class나 std::pair로 넘기자니 조잡하고, 문제의 의도가 아닌 것 같았습니다.

따라서 카운팅은 캐싱으로 해결하기로 하고, 함수는 최대 sum만 return 해서 TRIANGLEPATH 식으로 수행하기로 했습니다.

2. 아이디어

dp로 풀었습니다.

3. 코드 설명

https://github.com/Scaachan/Advanced-Algorithm-Study/blob/0eeec5a3adfb004dbd384dc69cb9a5d3044528aa/TRIPATHCNT/Scaachan.cpp#L11-L37

📌Line 21~24

	if (a == b) {
		cache_cnt = memo[y + 1][x][1] + memo[y + 1][x + 1][1];
		return cache_sum = tri[y][x] + a;
	}

삼각형을 트리로 생각할 때, 왼쪽 자식과 오른쪽 자식 노드의 sum이 같다면 cnt(카운팅 변수)를 합쳐줍니다.

현재 노드의 sum은 현재 노드의 값 + 왼쪽 or 오른쪽 자식노드의 sum입니다.

📌Line 25~28

	else if (a < b) {
		cache_cnt = memo[y + 1][x + 1][1];
		return cache_sum = tri[y][x] + b;
	}

오른쪽 자식 노드의 sum이 더 크다면, 현재 노드의 cnt는 오른쪽 자식 노드의 cnt나 다름없고

현재 노드의 sum은 현재 노드의 값 + 오른쪽 자식노드의 sum이 됩니다.

📌Line 29~32

	else {
		cache_cnt = memo[y + 1][x][1];
		return cache_sum = tri[y][x] + a;
	}

그 외의 경우라면, 왼쪽 자식노드의 cnt를 대입하고

현재 노드의 sum에는 현재 노드의 값 + 왼쪽 자식노드의 sum을 대입합니다.

📌Line 35~36

 cache_cnt = 1; 
 return cache_sum = tri[y][x]; 

35~36줄은 base case를 위한 로직입니다.

현재 노드가 leaf 일 때 더이상 내려갈 노드가 없으므로, cnt를 기본 1로 두고 자기 자신의 값을 sum으로 캐싱합니다.