알고리즘_코딩테스트/주간코딩 스터디 (주코스)
(Week5)[DP] 정수 삼각형
논곰
2022. 7. 7. 14:56
주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요
소요시간: 30분
1. 문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/43105
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우 찾기
2. 접근 방식
- 이전에 풀었던 문제여서 비교적 쉽게 풀었다.
점화식: $dp[i][j] = triangle[i][j] + max(dp[i-1][j], dp[i][j-1])$
△▲△ (빈 삼각형은 삼각형 값이 없는 부분)
▲▲ (right만 존재하는 경우와, left만 존재하는 경우)
3. 코드
def solution(triangle):
dp = [[0]*(i+1) for i in range(len(triangle))]
dp[0][0] = triangle[0][0]
for i in range(1, len(triangle)):
for j in range(len(triangle[i])):
left = 0 if j==0 else dp[i-1][j-1]
right = 0 if j==len(triangle[i])-1 else dp[i-1][j]
dp[i][j] = triangle[i][j] + max(left, right)
return max(dp[-1])
4. 코멘트
- DP는 먼저 점화식을 세워놓고 하면 문제 풀이가 쉬운 것 같다.
- 대개 0번를 채워놓고 1번째 인덱스부터 시작한다는 것을 생각하면 쉽다.
- 점화식: 어떤 수열의 항 사이에 성립하는 관계식을 의미한다.