1. 공부한 내용

문제1 - 99 클럽 - 정수 삼각형:

[ 문제 풀이 ]

이번 문제는 삼각형의 꼭대기부터 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 것이다. 여기서 핵심은 위에서부터 순서대로 내려오며, 그 포인트에서 최대 합을 갖을 수 있도록 경로를 탐색하는 것이다. 이를 위해 다음 값을 갱신할 때, 이전 층의 좌상, 좌우 값 중 더 큰 값을 택할 수 있도록 알고리즘을 설계했다.

나의 풀이는 다음과 같다.

1. 먼저 주어진 triangle과 크기가 같은 dp라는 list를 만들어 준다.

2. dp[0] = triangle[0]으로 시작 값을 지정해 준다.

3. 반복문을 통해, 각 층을 위에서부터 훑을 수 있도록, 층 내에서는 좌부터 우로 훑을 수 있도록 만들어 준다.

4. 판단

• 만약 제일 좌측 포인트라면, 이전 층의 제일 좌측 값을 그대로 채택하여 주어진 triangle[i][0]을 더해준다.
• 만약 제일 우측 포인트라면, 이전 층의 제일 우측 값을 그대로 채택하여 주어진 triangle[i][-1]을 더해준다.
• 그 외의 경우라면, 이전 층의 좌상과 좌우 중 더 큰 값과 현재 주어진 triangle[i][j] 값을 더해준다.

5. 값 도출: dp[-1] 중 가장 큰 값을 선택해 return 한다.