[programmers] 정수 삼각형

<정수 삼각형>

문제(출처: https://school.programmers.co.kr/learn/courses/30/lessons/43105)

 

 

 

문제 풀이

  - 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