[프로그래머스] 정수 삼각형 / python

1️⃣ 문제 설명

코딩테스트 연습 - 정수 삼각형

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는다.

아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다.

예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능하다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return

 

2️⃣ 풀이 전 계획과 생각

• 삼각형 triangle[i][j]→ i : 상하 위치 값 / j: 좌우 기준 위치 값
• [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

 

🤔 어떻게 방향에 따른 이동을 넘어갈 수 있을까?
      1로만 이동가능하게 체크해주기 위해서는 어떻게 할까?

 

💡 아래로 내려가 1로만 좌우 이동하게끔 처리하여, triangle[height][width]에 이동하는 방법

• 제일 왼쪽에 있을 경우 (height ≥1 and width = 0)
  • triangle[height - 1][width]에서 triangle[height][width]로 가기
• 제일 오른쪽에 있을 경우 (height ≥1 and height = weight)
  • triangle[height - 1][width-1]에서 triangle[height][width]로 가기
• 그 외
  1. triangle[height - 1][width - 1]에서 triangle[height][width]로 가기
  2. triangle[height - 1][width]에서 triangle[height][width]로 가기

 

💡 풀고 싶은 문제 정의

풀고자하는 문제 : dp[height][width]에서의 중 height가 마지막인 원소들 중에 max 값

점화식을 위한 문제 : dp[height][width]에 도달하기 위한 max 값

 ✔ 점화식

dp[height][width] = max(dp[height-1][width], dp[height-1][width-1]) + triangle[height][width]

✔ base

dp[0][0] = triangle[0][0]

✔ 구현해보자

if width == 0
    dp[height][width] = dp[height-1][width] + triangle[height][width]
elif width == triangle_width
    dp[height][width] = dp[height-1][width-1] + triangle[height][width]
else
    dp[height][width] = max(dp[height-1][width], dp[height-1][width-1]) + triangle[height][width]

dp 배열이 height-1 높이까지 다 채워졌으면, height가 마지막인 원소들 중에 max 값을 출력해준다.

 

3️⃣ 풀이

def solution(triangle): 
    # dp 테이블 초기화 
    dp = [[0] * len(triangle) for _ in range(len(triangle))] 
    dp[0][0] = triangle[0][0] 
    
    for height in range(len(triangle)):
        line_width = len(triangle[height])
        for width in range(line_width):
            if width == 0 : 
                dp[height][width] = dp[height-1][width] + triangle[height][width]

            elif width == line_width - 1 :
                dp[height][width] = dp[height-1][width-1] + triangle[height][width]

            else:
                dp[height][width] = max(dp[height-1][width], dp[height-1][width-1]) + triangle[height][width]
    return max(dp[-1])

 

4️⃣ 알게된 개념과 소감

• 아래로 내려가 1로만 좌우 이동하게끔 처리하는 패턴을 처음에 찾지 못했다.
  → 현재 위치와 그 전 위치를 보고 규칙을 찾자.