[백준/JS] 1932번 - 정수 삼각형

Pakxe·2023년 9월 25일

JavaScript baekjoon js

PS

목록 보기

6/16

문제

1932번 - 정수 삼각형

풀이

시도했던 풀이 1(실패 !)

row 반복(밑변 한 줄 씩)을 돌고 col 반복을 그 안에서 돈다. 현재 항의 왼쪽 위 대각 항과 오른쪽 위 대각 항을 비교해서 큰 값을 sum에 누적하는 방법이었다.

이 방법이 안되는 이유는 왼쪽 대각 항 값 === 오른쪽 대각 항 값 인 경우 더 앞을 보지 않으면 어디로 갈지 정할 수 없다.

시도했던 풀이 2

문제를 쪼개서 생각해보자.

외곽선이 그려진 항이 가질 수 있는 최대 누적합 어떻게 구해질까?

왼쪽 위 대각 항과 오른쪽 위 대각 항 둘 중 큰 값이 값이 합쳐져 누적합이 구해지게 된다.
왜냐면 이 외곽선이 그려진 항에 접근할 수 있는 항은 저 둘 밖에 없기 때문이다. 그럼 이렇게 역삼각형 영역(위쪽 두 항과 아래 항)만 생각해보면 된다.

원래 문제는 아래로 내려가면서 큰 값을 더해나가 최대 누적합을 구하는 문제다. 하지만 위 접근 법은 일단 이 항으로 내려오는건 확정! 그러면 위쪽 두 항중 어느항에서 내려오는게 최대인가?를 구하는 것이다. 어떻게 이 방법으로 문제를 해결할 수 있는 것일까?

(무지개 순서로 흐름을 봐보자)

현재 항에서 가능한 최대 누적합은 위쪽 두 항에서 값이 더 큰 항이 나를 향해 내려오는 것으로 구해질 수 있다. 그러면 이 위쪽 두 항중 왼쪽 항의 최대 누적합은 어떻게 구해질까? 똑같이 이 위쪽 항의 더 위쪽 두개의 항 중 큰 값이 내려오는 것으로 구해질 수 있다. 이렇게 각각의 항의 최대 누적합이 구해지게 된다. 일단 해당 항은 자신이 더할 수 있는 최선의 큰 값을 선택하여 저장했기 때문이다.

이렇게 생각한다면 모든 항들의 최대 누적합을 구하여 저장해야한다. 왜냐면 다음 줄(아래 줄)의 최대값을 구하기 위해선 지금 줄의 최대 누적합이 필요하기 때문이다.

이때 각각의 최대 누적합은 위에서부터 타고 내려오므로 제일 꼭짓점의 최대 누적 합부터 구하는 순서로 흐름을 잡았다. 결국 위에서부터 제일 아래까지 구하면 밑변의 항들은 각자 자신이 가질 수 있는 최대 누적합을 갖게되며, 이들 중 제일 큰 값이 문제의 답이 된다.

점화식

현재 최대 누적합 = max(왼쪽 위 최대 누적합, 오른쪽 위 최대 누적합) + 현재 항의 값

주의할 점

위 방식대로 코드를 작성할 때 제일 왼쪽 항, 제일 오른쪽 항은 더할 수 있는 값이 하나뿐이므로 이를 처리해줘야한다.

풀이

공간 복잡도를 줄이기 위해 입력을 저장하기 위한 배열에 최대 누적합을 덧씌워서 저장했다.

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = parseInt(input[0]); // 삼각형 높이

const pyramid = new Array(n).fill().map(() => []); // 입력 삼각형 값들과 dp 배열로 사용하기 위한 2차원 배열

// 피라미드 만들기
for (let i = 1; i <= n; i++) {
	const curRow = input[i].split(' ').map(Number);
	pyramid[i - 1].push(...curRow);
}

for (let i = 1; i < n; i++) {
	// 가로 변
	for (let j = 0; j < pyramid[i].length; j++) {
		// 단위 개수
		if (j === 0) {
			// 제일 왼쪽
			pyramid[i][j] = pyramid[i - 1][j] + pyramid[i][j];
		} else if (j === pyramid[i].length - 1) {
			// 제일 오른쪽
			pyramid[i][j] = pyramid[i - 1][j - 1] + pyramid[i][j];
		} else // 그 외 
			pyramid[i][j] =
				Math.max(pyramid[i - 1][j - 1], pyramid[i - 1][j]) + pyramid[i][j];
	}
}

console.log(Math.max(...pyramid[n - 1]));