Codie

백준, 프로그래머스에서 풀 수 있는 문제입니다.

🔎 힌트
- DP를 이용해보세요.
- BottomUp 방식을 이용해보세요.

풀이

▼

BottomUp 방식 풀이

TopDown 방식은 아래에서 위로 이동하면서 작은 문제를 해결하는 방식입니다.

배열의 첫 번째 값(array[0][0])이 답이 됩니다.

function solution(triangle) {
	const array = triangle.map(row => [...row]);
	
    for (let i = array.length - 2; i >= 0; i--) {
        for (let j = 0; j < array[i].length; j++) {
            const left = array[i+1][j];
            const right =  array[i+1][j+1]
            
            array[i][j] += Math.max(left, right);
        }
    }
    return array[0][0];
}

TopDown 방식 풀이

TopDown 방식은 위에서 아래로 이동하면서 작은 문제를 해결하는 방식입니다.

맨 위 작은 삼각형은 초기화해주었습니다. 마지막 배열의 최댓값이 답이 됩니다.

function solution(triangle) {
    const array = triangle.map(row => [...row]);
    
    array[1][0] = array[0][0]+array[1][0];
    array[1][1] = array[0][0]+array[1][1];

    for (let i = 2; i < array.length; i++) {
        for (let j = 0; j < array[i].length; j++) {
            if (j === 0) {
                array[i][j] += array[i-1][j];
                continue;
            }
            if (j === array[i].length - 1) {
                array[i][j] += array[i-1][j-1];
                continue;
            }
            const leftParent = array[i-1][j-1];
            const rightPerent =  array[i-1][j];
            array[i][j] += Math.max(leftParent, rightPerent);
        }
    }
    return Math.max(...array[array.length - 1])
}

TopDown 방식의 한계

프로그래머스 채점은 효율성 테스트6에서 시간 초과가 발생했습니다.

BottomUp 방식에 비해 조건문을 더 활용하는 문제가 있었습니다.

아래 방법으로 해결했습니다.

• 반복문 내부에서 조건문이나 계산을 최소화한다.
• inplace 수정 : 원본 배열(triangle)을 직접 수정하지 않고 복사해서 사용한다.
  *inplace는 원본 데이터를 새로운 메모리에 할당하지 않고 직접 조작하는 것을 말한다.

📍 이중 배열 복사하기

inplace를 해결하기 위해 깊은 복사를 사용했습니다.

const array = triangle.map((row) => [...row]);

이 문제는 BottomUp 방식을 사용하는 것이 성능에 더 유리했습니다.

반복문 내 조건 분기를 최소화하는 것이 중요했습니다.

🔗 문제 바로가기

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

프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/43105

🔗 레퍼런스

[프로그래머스] LV.3 정수 삼각형 (JS)