정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

 

I. 문제 개요

삼각형에 들어있는 숫자 중, 지나온 숫자들의 최대 합을 구하는 문제이다.

 

 

 

II. 알고리즘 설계 및 풀이

1. DP 점화식 설계

0행:  7
1행:  3  8
2행:  8  1  0

 

주어진 삼각형을 위와 같이 직각 삼각형으로 보자.

 

2행의 "8"은 1행의 "3"에서밖에 접근할 수 없다.

 

2행의 "1"은 1행의 "3", "8" 두 군데에서 접근할 수 있다.

 

2행의 "0"은 1행의 "8"에서만 접근할 수 있다.

 

현재 칸이 맨 처음 또는 마지막 칸이라면, 각각 바로 위, 왼쪽대각선 위의 숫자만 고려할 수 있다.

 

그 외의 칸이라면, 바로 위 또는 왼쪽 대각선 위의 숫자 둘 다 고려할 수 있다.

 

바로 위, 왼쪽 대각선 위의 숫자 중 더 큰 숫자를 택하여 현재 칸의 숫자와 더하는 방식을 통해, 원하는 최댓값을 찾을 수 있을 것이다.

 

if 왼쪽 끝단:
    dp[i][j] = 삼각형_현재칸의_숫자 + dp_바로윗칸의_숫자
    
elif 오른쪽 끝단:
    dp[i][j] = 삼각형_현재칸의_숫자 + dp_왼쪽대각선_위의_숫자
    
else:
    왼쪽대각선_위의_숫자를_택한경우 = dp_왼쪽대각선_위의_숫자 + 삼각형_현재칸의_숫자
    바로윗칸의_숫자를_택한경우 = dp_바로윗칸의_숫자 + 삼각형_현재칸의_숫자

    dp[i][j] = max(왼쪽대각선_위의_숫자를_택한경우, 바로윗칸의_숫자를_택한경우)

 

위의 알고리즘을 의사코드로 표현하면 위와 같다.

 

이재 이를 코드로 구현하면 된다.

 

2. 변수 초기화

n = len(triangle)
dp = [[0] * len(triangle[i]) for  i in range(n)]  # triangle 모양 따라 만들기

# dp 초기화
dp[0][0] = triangle[0][0]
dp[1][0] = triangle[1][0] + dp[0][0]
dp[1][1] = triangle[1][1] + dp[0][0]

 

탐색에 사용할 dp를 생성하고, 초기화한다.

 

dp의 1행에 들어있는 각 숫자에, 0행의 숫자를 더해준다.

 

그 이유는 dp에서 1행의 경우, 0행에 들어있는 숫자 1개만 받을 수 있기 때문이다.

 

3. DP 적용

for i in range(2, n):
    for j in range(0, i+1):
        if j == 0:         # 왼쪽 끝
            dp[i][j] = triangle[i][j] + dp[i-1][j] 
        elif j == i:	   # 오른쪽 끝
            dp[i][j] = triangle[i][j] + dp[i-1][j-1]
        else:              # 그 외
            from_above = dp[i-1][j] + triangle[i][j]   # 바로 위에서 넘어오는 경우
            from_left = dp[i-1][j-1] + triangle[i][j]  # 좌대각선 위에서 넘어오는 경우

            dp[i][j] = max(from_above, from_left)      # 둘 중 큰 값을 dp에 반영

ans = max(dp[-1])
return ans

 

dp의 2행부터 탐색을 시작한다.

 

j번째 숫자가 왼쪽 끝에 있다면, dp에서 바로 윗 행에 들어있는 숫자를 더해준다.

 

오른쪽 끝이라면, dp에서 왼쪽 대각선 위에 있는 숫자를 더해준다.

 

둘 다 아니라면, dp의 왼쪽 대각선 위에 있는 숫자와 현재칸의 숫자를 더한 값, 바로 윗 행의 숫자와 현재 숫자를 더한 수 중 더 큰 값을 dp에 집어넣는다.

 

최종적인 답안은 맨 끝 행에 들어있는 수 중, 가장 큰 수이다.

 

III. 전체 코드

def solution(triangle):
    # 2. 변수 초기화
    n = len(triangle)
    dp = [[0] * len(triangle[i]) for  i in range(n)]  # triangle 모양 따라 만들기

    # dp 초기화
    dp[0][0] = triangle[0][0]
    dp[1][0] = triangle[1][0] + dp[0][0]
    dp[1][1] = triangle[1][1] + dp[0][0]
    
    # 3. DP 적용
    for i in range(2, n):
        for j in range(0, i+1):
            if j == 0:         # 왼쪽 끝
                dp[i][j] = triangle[i][j] + dp[i-1][j] 
            elif j == i:	   # 오른쪽 끝
                dp[i][j] = triangle[i][j] + dp[i-1][j-1]
            else:              # 그 외
                from_above = dp[i-1][j] + triangle[i][j]   # 바로 위에서 넘어오는 경우
                from_left = dp[i-1][j-1] + triangle[i][j]  # 좌대각선 위에서 넘어오는 경우

                dp[i][j] = max(from_above, from_left)      # 둘 중 큰 값을 dp에 반영

    ans = max(dp[-1])
    return ans

 

IV. 풀이 결과