조예지

2.문제이름

3. 수행시간[초(s)]

3600

4. git 주소 URL

https://github.com/coastby/PCCP-study/commits/main

좋아요 누르기

좋아요 수

: 0

5 more properties

| 코드 작성하기

def solution(triangle):
    dp = triangle
    dp[0][0] = triangle[0][0]
    for i in range(len(triangle)):
        for j in range(i+1):
            if j == 0:
                a = 0
            else:
                a = triangle[i-1][j-1]
            if j == i:
                b = 0
            else:
                b = triangle[i - 1][j]
            val = max(a, b)
            dp[i][j] = triangle[i][j] + val
    return max(dp[len(triangle)-1])
Java
복사

| 코드 설명하기

•

처음에는 큰 수만 따라갔는데 문제에서는 인접한 수로만 이동이 가능하다는 조건이 있었다.

•

마냥 큰 수만 쫓는 것은 그리디로 그 다음줄에 더 큰 수가 나오면 틀린 풀이법이 된다. 

•

모든 경우의 수를 찾기 위해서는 triangle과 같은 배열에 최대합을 저장하는 방법을 사용해야 했다.

위에서 가져올 수 있는 두 수 중에 큰 수와 현재 위치를 더해서 dp에 저장하였다.

양쪽 끝에 있는 수는 비교할 수가 하나만 있으므로 이에 맞는 처리를 해주었다.

이러한 처리를 안하기 위해서는 아래처럼 밑에서 올라가는 방법이 좋을 것 같다.

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
Python
복사