정수 삼각형

날짜 : 2023. 10. 03

사용 언어 : python

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=python3

 

 

코드

def solution(tri):
    r = len(tri)
    res = [[0] * i for i in range(1, len(tri) + 1)]
    res[0] = tri[0]
    for i in range(len(tri)-1):
        for j in range(i + 1):
            now = res[i][j]
            left = tri[i+1][j]  # 왼쪽 아래의 수
            res[i+1][j] = max(now + left, res[i+1][j])
            right = tri[i+1][j+1]  # 오른쪽 아래의 수
            res[i+1][j+1] = max(now + right, res[i+1][j+1])
    # for i in res:
    #     print(i)
    return max(res[-1])

 

 

풀이

- 전형적인 DP 문제이다.

- 위 그림과 같이 임의의 점 (i, j)의 케이스에서는 각각 왼쪽으로는 (i+1, j)가 해당되고, 오른쪽으로는 (i+1, j+1)이 해당된다.

- 각각의 row별로 max값을 갱신해야 하기 때문에 미리 값들을 0으로 초기화하여 max() 함수를 사용해 최신화하기 쉽게 설정한다.

- 그 다음 2중 for문을 사용해서 갱신해 나가고, 마지막에는 가장 아래의 row에서 최대값을 리턴하는 방식으로 답을 출력하면 된다.

 

 

알게된 점

- 값들을 갱신하지 않고 임의의 리스트 tmp를 만들어서 각 row별로 넣는 방식으로 문제를 풀었다.

- 케이스가 하나였고 그 케이스는 바로 맞아서 제출했지만 오답이 나왔고, 그덕에 틀렸던 부분을 찾을 수 있었다.

- 만약 실제 코딩테스트였다면 틀린 채 넘어갔을 수 있기 때문에 한번에 맞힐 수 있도록 노력해야겠다.

 

 

참고 사이트

-