Programmers_43105 정수 삼각형

• TOC {:toc}

이 글은 프로그래머스의 43105번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2024.04.10

정확성 테스트

효율성 테스트

function solution(triangle) {
    let dp = [0];

    for (line of triangle) {
        const newDp = [];
        for (let i = 0; i < line.length; i++) {
            newDp.push(line[i] + Math.max(dp[i - 1] ?? 0, dp[i] ?? 0));
        }
        dp = newDp;
    }

    return Math.max(...dp);
}

아이디어 & 풀이

triangle의 각 줄을 순회하면서 각 숫자까지 도달하는 데 거친 경로의 최댓값을 업데이트 한다. 현재까지 거친 경로의 최댓값을 저장하는데 동적계획법을 이용한다.

• 이를 위해서 현재 줄에서 각 값에 접근할 수 있는 거치는 여러 경로 중 최댓값을 고르면 된다.
• 즉, 현재 줄의 값들을 기준으로 각 값에 도달했을 때 가질 수 있는 최댓값으로 dp 배열을 업데이트 한다.

dp 배열의 업데이트는 다음과 같이 이뤄진다.

• triangle에서 경로를 이동할 때 대각선으로 인접한 수로 밖에 이동하지 못한다. 이를 배열의 관점에서 표현하기 위해 예시를 이용해 살펴보면 다음과 같다.

  인덱스	0	1	2	3	4
  line 1	7
  line 2	3	8
  line 3	8	1	0
  line 4	2	7	4	4
  line 5	4	5	2	6	5

• 이동할 수 있는 경로를 가시화하면 다음과 같다.

  7 
  | \
  3  8 
  | \| \
  8  1  0 
  | \| \| \
  2  7  4  4 
  | \| \| \| \
  4  5  2  6  5 
  

• 위의 관계를 봤을 때 다음 줄의 i번쨰 수에 도달하는 경로는 이전 줄에서 i - 1번째 수와 i번째 수를 거친 경로이다.

• 그러므로 현재 줄의 i번째 수를 거치는 수 중에서 최댓값을 갖는 경로는 이전 줄에서 i - 1을 거치는 경로와 i를 거치는 경로중 더 큰 값을 갖는 경로를 선택해 현재의 수를 더한 경로라고 볼 수 있다.

• 즉 dp 배열의 업데이트는 다음과 같은 관계로 이뤄진다.

  • newDp[i] = Math.max(prevDp[i - 1], prevDp[i]) + 현재 숫자 이다.
  • 이때, 첫 원소나 마지막 원소의 경우 이전 혹은 다음 원소가 존재하지 않을 수 있으므로 prevDp[i] ?? 0과 같이 값이 존재하지 않는 경우에 0을 반환할 수 있도록 해준다.

• 주어진 테스트케이스로 각 줄마다 업데이트 되는 dp 값을 나타내면 다음과 같다.

  인덱스	0	1	2	3	4
  line 1	7
  line 2	10 (3 + 7)	15 (8 + 7)
  line 3	18 (10 + 8)	16 (15 + 1)	15 (15 + 0)
  line 4	20 (18 + 2)	25 (18 + 7)	20 (16 + 4)	19 (15 + 4)
  line 5	24 (20 + 4)	30 (25 + 5)	27 (25 + 2)	26 (20 + 6)	24 (19 + 5)

위와 같은 방식으로 각 줄마다 dp 배열을 업데이트 한 뒤 마지막 dp에서 Math.max를 이용해 최댓값을 구하면 된다.

참고 답안

정확성 테스트

효율성 테스트

function solution(triangle) {
    return Math.max(
        ...triangle.reduce((dp, line) => {
            return line.map((num, i) => {
                return num + Math.max(dp[i - 1] ?? 0, dp[i] ?? 0);
            });
        }, [])
    );
}

• reduce를 이용해 dp 배열을 업데이트 했다.