문제 유형

  • 다이내믹 프로그래밍

문제 설명

https://grepp-programmers.s3.amazonaws.com/files/production/97ec02cc39/296a0863-a418-431d-9e8c-e57f7a9722ac.png

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

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

제한사항

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

알고리즘 유도

https://i.ibb.co/ysm6QBp/001.jpg

정방향으로 생각하면

한 방향에서 오는 경우엔 무조건 위 노드의 가중치를 이어받게 되며,

두 방향에서 오는 경우엔 자신의 가중치와의 합이 더 큰 방향으로 결정된다.

https://i.ibb.co/j4YGXwJ/002.jpg

https://i.ibb.co/2d8mgPf/003.jpg

https://i.ibb.co/cyP6g2N/004.jpg

역방향으로 생각하면

방향성 그래프라 정방향으로 풀어야할거 같지만 사실 역방향으로 생각해도 정답이 달라지지 않는다.

오히려 역방향으로 생각하면 모두 일관성 있게 가중치를 업데이트 할 수 있다.

https://i.ibb.co/NCCkN0s/005.jpg

https://i.ibb.co/SQb51x6/006.jpg

https://i.ibb.co/MpfgSRh/007.jpg

알고리즘 코드 (정방향)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(triangle):    
    D = [[triangle[0][0]]]
    
    for t in triangle[1:]:
        D.append([0] * len(t))
    
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                D[i][j] = D[i-1][0] + triangle[i][j]
            elif i == j:
                D[i][j] = D[i-1][j-1] + triangle[i][j]
            else:
                D[i][j] = max(D[i-1][j-1] + triangle[i][j], D[i-1][j] + triangle[i][j])
                
    return max(D[-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
정확성  테스트
테스트 1 〉 통과 (0.02ms, 10.3MB)
테스트 2 〉 통과 (0.03ms, 10.3MB)
테스트 3 〉 통과 (0.05ms, 10.2MB)
테스트 4 〉 통과 (0.18ms, 10.3MB)
테스트 5 〉 통과 (1.33ms, 10.6MB)
테스트 6 〉 통과 (0.58ms, 10.3MB)
테스트 7 〉 통과 (1.38ms, 10.4MB)
테스트 8 〉 통과 (0.29ms, 10.3MB)
테스트 9 〉 통과 (0.02ms, 10.2MB)
테스트 10 〉 통과 (0.17ms, 10.3MB)
효율성  테스트
테스트 1 〉 통과 (48.19ms, 18MB)
테스트 2 〉 통과 (36.61ms, 16.1MB)
테스트 3 〉 통과 (54.10ms, 18.8MB)
테스트 4 〉 통과 (49.26ms, 18.1MB)
테스트 5 〉 통과 (44.85ms, 17.4MB)
테스트 6 〉 통과 (48.78ms, 19.3MB)
테스트 7 〉 통과 (50.64ms, 18.7MB)
테스트 8 〉 통과 (41.84ms, 17MB)
테스트 9 〉 통과 (40.67ms, 17.4MB)
테스트 10 〉 통과 (51.98ms, 18.6MB)
채점 결과
정확성: 64.3
효율성: 35.7
합계: 100.0 / 100.0

알고리즘 코드 (역방향)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(triangle):    
    triangle.reverse()
    D = [triangle[0]]
    for t in triangle[1:]:
        D.append([0] * len(t))
    
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            D[i][j] = max(
                D[i-1][j] + triangle[i][j], 
                D[i-1][j+1] + triangle[i][j]
            )
        
    return D[-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
정확성  테스트
테스트 1 〉 통과 (0.02ms, 10.2MB)
테스트 2 〉 통과 (0.03ms, 10.2MB)
테스트 3 〉 통과 (0.05ms, 10.2MB)
테스트 4 〉 통과 (0.27ms, 10.4MB)
테스트 5 〉 통과 (1.22ms, 10.5MB)
테스트 6 〉 통과 (0.35ms, 10.3MB)
테스트 7 〉 통과 (2.22ms, 10.4MB)
테스트 8 〉 통과 (0.31ms, 10.3MB)
테스트 9 〉 통과 (0.03ms, 10.2MB)
테스트 10 〉 통과 (0.16ms, 10.2MB)
효율성  테스트
테스트 1 〉 통과 (42.15ms, 17.9MB)
테스트 2 〉 통과 (32.54ms, 16.1MB)
테스트 3 〉 통과 (44.09ms, 19MB)
테스트 4 〉 통과 (43.34ms, 17.8MB)
테스트 5 〉 통과 (35.18ms, 17.5MB)
테스트 6 〉 통과 (49.00ms, 19.2MB)
테스트 7 〉 통과 (46.93ms, 18.6MB)
테스트 8 〉 통과 (38.40ms, 17MB)
테스트 9 〉 통과 (40.11ms, 17.4MB)
테스트 10 〉 통과 (42.12ms, 18.7MB)
채점 결과
정확성: 64.3
효율성: 35.7
합계: 100.0 / 100.0