[BOJ] 1932 - 정수 삼각형

문제

아래 링크를 통해 문제를 먼저 풀어보고 옵시다!

https://www.acmicpc.net/problem/1932

문제 분석

---

규칙찾기

첫 번째 줄은 7밖에 없으니 7이 유일한 경로이고, 최대합은 7이겠네요.

두 번째 줄은 3을 선택할 때는 대각선 우측인 7을, 8을 선택할 때는 대각선 좌측인 7을 선택해서 각각 10과 15가 최대합이 되겠습니다.

아하, 현재 숫자를 기준으로 이전 줄의 좌, 우의 선택만 가능하군요.

현재 숫자의 인덱스를 i라고 한다면, 이전 줄의 좌측은 i-1, 우측은 i의 인덱스겠네요. 오케이 감이 잡히기 시작합니다.

최적의 경로를 찾아야 하나

문제에서는 최대가 되는 경로를 구하라 했지만, 답으로는 최대가 되는 값만 구하면됩니다.

우리는 경로라는 표현에 헷갈리지 말고, 어떻게하면 최대값을 찾을 수 있을지 생각해봅시다.

각 줄에서 최대인 값을 선택하고, 다음줄에서도 그 값을 쓰면 되지 않을까요?

좋은 생각입니다. 각 줄에서 최대값을 기억한다는 점에서 좋은 시도였습니다.

하지만 조건이 이전 줄의 좌우 대각선의 숫자 두개만 고려하라고 했으니, 위 아이디어를 바로 적용하기에는 무리가 있어 보입니다.

그리고 현재까지 최대값이라해서, 다음 줄까지도 그 값이 최대일거라는 보장은 없습니다. 줄이 바뀜에 따라 값은 업데이트되니까요.

이전 수행의 값을 하나만 기억하는 것은 적절하지 않은 접근법이군

그러고보니 이 문제는 이전에 풀었던 "BOJ-1149-RGB거리"문제 와 비슷합니다.

현재의 최적의 선택은 과거의 누적된 결과에 영향을 받고, 미래에는 어떤 선택을 할 지 모른다는 점에서 말이죠.

그래서 풀이자는 별도의 메모리공간에 현재 선택할 수 있는 모든 결과를 기록 하는 방식으로 미래의 선택에 대비합니다.

곧, DP 문제가 되겠네요.

알고리즘 전략

---

우리는 DP 알고리즘과 관련된 문제라는 것을 깨달아버렸습니다.

dp테이블 만들기

그러면 먼저 dp 테이블을 구성해야죠. N개의 줄에는 N개의 숫자가 나열되니, 우리는 N+1* N 크기의 2차원 배열을 만들어줍시다.

const dp = Array.from({ length: N + 1 }, () => Array.from({ length: N }, () => 0))

자바스크립트에서 배열을 만드는 방법은 리터럴로 선언하여 만들기(const array = [1,2,3]과 같이) 뿐 아니라, Array.from()을 활용하는 방법, Array객체의 생성자 함수를 이용한 new Array()방법이 있는데요, 저는 Array.from을 사용하는게 2차원 배열을 동적으로 생성할 때 가독성이 더 좋다생각해 이 방법을 사용하고 있습니다. 핵심은 2차원 배열의 내부 배열이 각각 다른 참조값을 가지는 새로운 배열이라는 점!

약간의 TIP

row개수를 N+1로 한 데에는 이유가 있습니다.

• N번째 수행과 순회 시 인덱스값을 동일하게 만들어주기 위함
• 첫 번째 줄의 dp 로직 수행에 대한 예외 케이스 로직을 만들지 않기 위함

첫 번째 이유는 금방 이해가 가실거에요. 그런데 두 번째는 무슨 말이냐 하면,

N개의 row로 dp 테이블을 만들 때

----	i=0	i=1	i=2...
n = 0	7	0	0
n = 1	10	15	0
n = 2	18	16	15
n = 3	...	...	...

n번째 수행에서는 n-1번째 수행에 대한 값을 참조하여 로직을 진행해야 합니다.

그런데 N개의 row로 dp테이블을 만들 때는 첫 번째 수행에 대한 row의 인덱스가 0이기에, 참조할 이전 row가 없어요. n = -1이라는 인덱스가 없으니까요.

그래서 dp업데이트 로직에 n=0(첫 번째 줄)일 때의 수행시에는 예외를 두는 로직을 짜야해요.

N+1개의 row로 dp 테이블을 만들 때

----	i=0	i=1	i=2...
n = 0	0	0	0
n = 1	7	0	0
n = 2	10	15	0
n = 3	18	16	15
n = 4	...	...	...

그런데 이렇게 N+1개의 row로 dp 테이블을 만들면,
n=1이 첫 번째 줄에 대응되니까 이전 줄인 n=0의 값들이 존재하잖아요? dp테이블 업데이트 로직을 예외로직 추가 없이 일관되게 적용할 수 있어요.

성공한 풀이

---

const directory = process.platform === 'linux' ? 0 : __dirname + '/test.txt'
const input = require('fs').readFileSync(directory).toString().trim().split('\n')
const N = input[0] * 1

const dp = Array.from({ length: N + 1 }, () => Array.from({ length: N }, () => 0))

for (let n = 1; n < N + 1; n++) {
  const currRow = input[n].split(' ').map(Number)
  for (let i = 0; i < n; i++) {
    const prevLeftIndex = i - 1
    const prevRightIndex = i
    const hasLeft = prevLeftIndex >= 0 && prevLeftIndex < n
    const hasRight = prevRightIndex >= 0 && prevRightIndex < n
    const selectedPrevNum = Math.max(
      hasLeft ? dp[n - 1][prevLeftIndex] : 0,
      hasRight ? dp[n - 1][prevRightIndex] : 0,
    )
    dp[n][i] = currRow[i] + selectedPrevNum
  }
}

console.log(Math.max(...dp[N]))