프로그래머스 고득점 kit - 정수 삼각형

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangle                                                                                           result

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

30

 

풀이

function acc(downstair, arr) {
  const temp = [];
  for (let i = 0; i < downstair.length; i++) { // downstair 개수로 증가
    if (i === 0) { // 맨 앞
      const val = arr[i] + downstair[i];
      temp.push(val);
    } else if (i === downstair.length - 1) { // 맨 끝
      const val = arr[i - 1] + downstair[downstair.length - 1];
      temp.push(val);
    } else {
      const val1 = arr[i] + downstair[i]; // 15, 1 = 16
      const val2 = arr[i - 1] + downstair[i]; // 10 1 = 11
      temp.push([val1, val2].sort((a, b) => b - a)[0]);
    }
  }

  return temp;
}


function solution(triangle) {
  let arr = triangle[0];
  for (let i = 1; i < triangle.length; i++) {
    arr = acc(triangle[i], arr);
  }
  return Math.max(...arr);
}

 

접근 방법

 

1. 처음에는 트리의 맨 위에서부터 하나씩 다 더해서 트리를 넓혀나갔다.

예를 들면 이런식이다.

 

arr 7
arr 10,15
arr 18,11,16,15
arr 20,25,18,15,20,20,19,NaN

 

누적해서 더해서 나온 결과를 모두 수집했다.

이렇게 하면 테스트 케이스는 통과하지만 제출시 7.1점을 맞는다.

 

그래서 2번째로는 값을 서로 비교해서 큰 값만 남겨두었다.

 

[7]

3, 8

8, 1, 0 

2, 7, 4, 4

4, 5, 2, 6, 5

이렇게 되어 있을때

 

위에서부터 하나씩 바꿔본다.

 

              7

          10, 15                ----- 바꾼 지점

       8     1     0

   2,     7  , 4,      4

4,    5   , 2,     6,      5

 

 

 

                                    7

             10,                                      15 

       18    (11과 16을 비교해서 놓는다.)    15           ---- 바뀐 지점

   2,      7,                                           4,      4

4,    5,                          2,                         6,      5

 

이렇게 양쪽 끝에 있지 않은 숫자는 

더한 값을 비교해서 놓는다.

 

그렇게 반복하면

 

리프 부분은 [ 24, 30, 27, 26, 24 ] 이렇게 된다.

 

그럼 여기서 제일 큰 수를 리턴한다.