[Python/프로그래머스]정수 삼각형 _DP

 

 

 

 

 

 

문제 : 

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

 

 

 

 

 

코드 : 

 

def solution(triangle):
    answer = 0
    for i in range(1, len(triangle)) :
        for j in range(len(triangle[i])) :
            if j == 0 : # 왼쪽 끝 원소 
                triangle[i][j] += triangle[i-1][j]
            elif j == len(triangle[i])-1 : # 오른쪽 끝의 원소
                triangle[i][j] += triangle[i-1][j-1]
            else : 
                triangle[i][j] += max(triangle[i-1][j-1] , triangle[i-1][j])
            
    answer = max(triangle[-1])
            
    return answer

 

 

 

이런 dp 문제 오랜만이다.

3학년 알설에서 배웠던 dp가 새록새록 떠오른다. 

 

 

 

 

 

풀이법 : 

 

2차원 그래프로 triangle을 보고

<예외처리>

가장 왼쪽, 가장 오른쪽인 경우 인덱스 에러가 나지않게 처리해준다.

 

( 맨 왼쪽의 원소는 윗줄에서 왼쪽의 원소에서 밖에 내려올 수 없다. 

맨 오른쪽 원소는 윗줄의 가장 오른쪽 원소에서 밖에 내려올 수 없다.) 

 

그렇게 값을 더하고 최종 triangle의 마지막줄의 max값을 반환한다. 

 

 

 

 

 

 

 

 

복습 때 만든 코드(1) : 

 

 

def solution(triangle):
    answer = 0
    for i in range(1,len(triangle)) :
        for idx, val in enumerate(triangle[i]) :
            if idx == 0 :
                triangle[i][idx] += triangle[i-1][idx]
            elif idx == len(triangle[i])-1 :
                triangle[i][idx] += triangle[i-1][idx-1]
            else :
                triangle[i][idx] += max(triangle[i-1][idx-1],triangle[i-1][idx])
    
    answer = max(triangle[-1])
    return answer

 

val은 쓰지도 않을건데 idx를 써야하니까 enumerate를 이용해서 만들었다. 

원래 코드가 더 좋은듯하다. 

 

 

 

복습 때 만든 코드 (2):

def solution(triangle):
    answer = 0
    for i in range(1,len(triangle)) :
        for j in range(0,i+1) :
            if j == 0:
                triangle[i][j]+= triangle[i-1][j]
            elif j==i :
                triangle[i][j] += triangle[i-1][j-1]
            else :
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
    answer = max(triangle[-1])
            
    return answer

 

두번째 for문에서 range안에 len(triangle[i]) 가 아닌 i를 이용해서 풀어봤다. 

 

 

 

 

유의점 : 

 

1. max(triangle[-1]) 

 

-1 을 하면 가장 마지막 원소가 나온다는 것을 계속 잊는다. 

 

 

 

 

 

 

참고 블로그 : 

 

https://velog.io/@younge/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A0%95%EC%88%98-%EC%82%BC%EA%B0%81%ED%98%95-%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95

[Python] 프로그래머스 - 정수 삼각형 (동적계획법)

 

 

복습 : 

✅20220618

✅ 20220620

✅ 20220622

✅ 20220624

✅ 20220626