🪴 Hayul's digital garden

Search

Search IconIcon to open search

정수 삼각형

Last updated Nov 8, 2022 Edit Source

스크린샷 2018-09-14 오후 5.44.19.png

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

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

# 제한사항

# 입출력 예

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

# 나의 오답

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def solution(triangle):
    curr_answer = 0
    k = 0
    for i in range(len(triangle)-1, 1, -1):
        if k not in [0, len(triangle[i])-1]:
            triangle[i-1][k-1] += triangle[i][k]
            triangle[i-1][k] += triangle[i][k]

        elif k == 0:
            triangle[i-1][k] += triangle[i][k]
        else:
            triangle[i-1][k-1] += triangle[i][k]
        k += 1
        if k == len(triangle[i])-1:
            k = 0
    left = triangle[0][0] + triangle[1][0]
    right = triangle[0][0] + triangle[1][1]
    prev_answer = max(left, right)
    if prev_answer > curr_answer:
        curr_answer = prev_answer
    
    return curr_answer

이건 오답이다. 아래의 정답과 비교하자.

# 다른 사람의 풀이

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def solution(triangle):

    height = len(triangle)

    while height > 1:
        for i in range(height - 1):
            triangle[height-2][i] += max([triangle[height-1][i], triangle[height-1][i+1]])
        height -= 1

    answer = triangle[0][0]
    return answer

나도 이렇게 삼각형을 거꾸로 시작하는 방법을 생각했는데… for i in range(len(triangle)-1, 1, -1): 이런 걸로 하나하나 내려갈 필요 없이, while height > 1:으로 한 다음, height -= 1으로 내려가면 되었구나. 괜히 복잡하게 생각했다.

그리고 따로 DP 테이블 을 사용할 필요 없이, 아래 칸의 값을 현재 칸의 좌 우의 값의 합으로 저장해버리면 된다. 나는 여기에서 뺄셈을 사용하는 바람에 조건문이 더 추가되어 버렸는데, 그냥 i + 1로 해버려도 된다.

Backlinks

Interactive Graph