[프로그래머스 - JS,PYTHON] level.3 정수 삼각형

 

 

프로그래머스

---

나의 풀이 

프로그래머스에서는 해당 문제를 자바스크립트로 풀 수 없다.  그래서 vscode에서 자바스크립트로 풀고 파이썬으로 코드를 변경하였다. 

DP를 방금 공부해서 어떻게 풀어야겠다는 바로 생각이났는데  코드로 표현하는데 시간이 걸렸다. 

 

DP를 모르시면 참고!

Dynamic Programming (DP)

 

풀이 설명

 

 

for문을 돌면서 triangle 배열을 그때 그때 최대값으로 변경을 해주었다.  

각각의 숫자는 왼쪽 아래 대각선 또는 오른쪽 아래 대각선 이 두가지 선택지 뿐이다.  

그래서 i = 1부터 시작하면서   두 번째줄 3하고 8이 있는데 3은 왼쪽 대각선이 없으니 오른쪽 대각선 7밖에 선택하지 못한다.  

이렇게 쭉 진행이되어서 i = 4  즉 다섯번째줄에서  4는 20 밖에 선택할수 없어서 24이고   5는 20 또는 25를 선택할 수 있다. 

그런데 최댓값을 구해야하니 25를 선택해야한다.  그 다음 2는 25 또는 20을 선택할 수 있는데 최댓값을 구해야하니 25을 선택한다.  

 

이런식으로 진행한뒤에 이중 배열 안에 맨 마지막 index에서 Max값을 구하면 그게 정답이 된다. 

 

 

 

자바스크립트 코드

function solution(triangle) {
  for (let i = 1; i < triangle.length; i++) {
    for (let j = 0; j < triangle[i].length; j++) {
      const firstCase = triangle[i - 1][j - 1] ?? 0;
      const secondCase = triangle[i - 1][j] ?? 0;

      if (secondCase >= firstCase) {
        triangle[i][j] += secondCase;
        continue;
      }
      triangle[i][j] += firstCase;
    }
  }
  return Math.max(...triangle.at(-1));
}

 

 

파이썬 코드

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            firstCase = triangle[i - 1][j - 1] if j > 0 else 0
            secondCase = triangle[i - 1][j] if j < len(triangle[i - 1]) else 0

            if secondCase >= firstCase:
                triangle[i][j] += secondCase
            else:
                triangle[i][j] += firstCase

    return max(triangle[-1])