[홀로 하는 코딩 공부] 정수 삼각형(Python)

 

프로그래머스

사용 언어: Python

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

프로그래머스

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 처음에는 아래와 같이 작성해보았다. 

def solution(triangle):
    if len(triangle) == 1:
        return triangle[0]
    
    answer = 0
    dp = []
    dp.append(triangle[0])

    for i in range(1, len(triangle)):
        tmp = []
        for j in range(i):
            tmp.append(dp[i-1][j] + triangle[i][j])
            tmp.append(dp[i-1][j] + triangle[i][j+1])
        dp.append(tmp)
    answer = max(dp[-1])
    
    return answer

 

▶ 처참하게 실패가 많이 뜬다. 원인 파악을 위해 우선 dp에 저장된 값을 확인하기 위해 출력해본다.

 

▶ 위와 같이 출력해보니 단번에 알겠다.

  - 첫번째 줄은 1개, 두번째 줄은 2개, 세번째 줄은 3개 이렇게 값이 되어야한다.

  - 어떤 값이 있다면 왼쪽 위의 값하고 더한 값을 dp에 추가하고, 오른쪽 위의 값하고 더한 값을 dp에 또 추가하였다.

  - 어떤 값이 있다면 왼쪽 위의 값하고 오른쪽 위의 값 중 더 큰 값을 본인 자체와 더하여 dp에 저장하여야 한다.

 

▶ 수정에 앞서서, 왼쪽 위의 값하고 오른쪽 위의 값 중 더 큰 값을 선별하는 부분을 작성해야 한다. 해당 부분을 테스트 하기 위해 기존 테스트 케이스가 아닌 다른 테스트 케이스를 아래와 같이 추가한다.

 

▶ 수정하여 아래와 같이 작성하였다.

def solution(triangle):
    if len(triangle) == 1:
        return triangle[0]
    answer = 0
    dp = [[0]*i for i in range(1, len(triangle)+1)]
    dp[0] = triangle[0]

    for i in range(1, len(triangle)):
        dp[i][0] = dp[i-1][0] + triangle[i][0]
        dp[i][i] = dp[i-1][i-1] + triangle[i][i]
        for j in range(1, i):
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

    answer = max(dp[-1])

    return answer

 

 

 

▶ 테스트 케이스 1번의 경우 dp를 출력하면 아래와 같이 나와야 한다.

 

 

▶ 테스트 케이스 2번의 경우 dp를 출력하면 아래와 같이 나와야 한다.

 

 

▶처음 테스트 케이스만 주어졌다면, 맞혔다 생각하고 넘어갔을 것이다. 항상 다 풀었다고 끝내지 말고 코드를 다시 한번 검토하는 습관을 들여야겠다.

 

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.