[programmers] 정수 삼각형

코딩 테스트 연습 - 동적 계획법(Dynamic Programming)

 

---

<정수 삼각형>

문제 설명

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중,
거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다.
아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.
예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때,
거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

 

제한 사항

 

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

 

문제 풀이

  - my solution

def solution(triangle):

    dp=[triangle[0]] #첫번째 줄 그대로
    for i in range(len(triangle)-1):
        temp=[]
        for j in range(i+1):
            if j>0: #왼쪽 대각선
                if temp[-1]<dp[i][j]+triangle[i+1][j]: #앞에서 더한 값 보다 더 크면
                    temp[-1]=dp[i][j]+triangle[i+1][j] #업데이트
            else: # 왼쪽 대각선
                temp.append(dp[i][j] + triangle[i + 1][j])
            temp.append(dp[i][j]+triangle[i+1][j+1]) #오른쪽 대각선
        dp.append(temp) 

    return max(dp[-1]) #마지막 줄에서 최댓값 출력

 

예전에 이와 비슷한 문제를 풀어본 적이 있어 문제 해결 방법을 쉽게 생각해낼 수 있었다.

dp를 활용하는 것이다! 물론 문제 제목에서 '동적 계획법'이라 나와있어 당연하다 생각할 수 있지만

문제를 보고 '아 dp를 활용해야겠다'라고 떠올랐단 말이다!

 

• 첫 번째 줄은 배열에 그대로 넣어준다.
• 왼쪽 대각선, 오른쪽 대각선 둘 중 하나로만 이동이 가능하므로 경우를 나눠준다
• 맨 왼쪽 대각선으로 가는 경우 다른 경우가 없으므로 배열에 넣어준다.
• 오른쪽 대각선과 왼쪽 대각선 중 큰 값으로 배열을 업데이트해준다.
• 마지막 줄에서 최댓값을 출력

 

그림으로 설명하면 말보다 쉬울 것 같지만 나중의 내가 글만 봐도 이해할 수 있을 거라 생각한다😏

---

생각🤔

 

이 문제는 백준과 프로그래머스에 둘 다 출제되어있다.

프로그래머스에서는 Level 3, 백준에서는 실버 1

 

문제를 풀면서 얻은 것 

1.  dp 활용

---

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges