[Python] 백준(BOJ) 1932번 - 정수 삼각형

링크

https://www.acmicpc.net/problem/1932

난이도(solved.ac 참고)

실버1

풀이

이 문제를 풀 때 처음에 좀 막막했다. 예제 입력에서 제일 꼭대기층 7에 대해 그 아래층의 3과 8중에 어디를 가야될지를 고민을 많이 했다. 그리디처럼 생각을 하고 가장 큰 값만 집어넣자니 범위 설정이 되어있어서 그렇게 할 수 없었다.

 

근데 생각해보니까, 최종합이 가장 큰 경로로 가기 위해 꼭 매 층마다 어떤 수를 넣어야될지 고려할 필요는 별로 없었다. 단지, 쭉쭉 직접 값을 구하면서 내려가면서 더 큰 값을 집어넣기만 하면 되는 것이었다.

예를 들면

  7
3  8

이 2층짜리 삼각형이 있다고 한다면 아래로 내려가면서 각각을 더해주는 것이다.

   7
10 15

이렇게 말이다. 이런식으로 더해나가는 과정을 반복하여 마지막 줄(맨 아랫줄)에 있는 값들 중 가장 큰 값을 출력해내면 되는 문제였다.

 

여기에서 j가 0일 때와 i일 때로 나눈 이유는, 삼각형 각 층마다 양 가장자리 부분에 대해서는 비교를 해 줄 필요가 없이 그냥 위층의 dp 값에다가 a 리스트의 값을 더해준 값을 새롭게 dp에 부여해주면 되기 때문이다. 문제 설명의 예시를 들어 설명하면,

    7
   3 8
  8 1 0
 2 7 4 4

이렇게 4층짜리가 있다고 하자. 이 경우 1, 2, 3층의 양 가장자리 부분(처음과 끝부분)은 그냥 위층의 값에서 더해주면서 내려가기만 하면 된다는 것이다. 그리고 그 결과는 아래와 같다.

        7
    10   15
  18   1   15
20  7  4   19

이제 양 가장자리가 아닌 경우에 대해 생각해 봐야 한다. 근데 이 부분도 사실 별로 어려울 건 없다.

단지, 2층의 1을 기준으로 설명하면 위층의 10과 15 중 더 큰 값에 자신이 가지고 있는 값(1)을 더해주면 되는 것이다.

이 방식을 유지하면 된다. 아래는 지금까지 설명한 부분을 코드로 나타낸 것이다.