문제:
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중,거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
풀이 방법:
양쪽 끝의 숫자들은 다음과 같이 그 전 칸의 처음 혹은 끝의 영향만을 받는다. 따라서 별도의 비교 없이 업데이트 해가면 된다.
2. 그 외의 경우
가운데에 있는 숫자들은 두 개의 숫자를 비교를 해야 한다. 가장 큰 경우를 구해야 하므로 둘 중 큰 경우를 선택해서 더해주면 된다.
위의 규칙을 따라서 다음과 같은 순서로 진행이 된다.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
예시와 같이 이러한 삼각형이 있다고 하면 처음에는 양쪽 끝에만 영향을 주는 경우 이므로 7을 각각 더해준다.
7
10 15
8 1 0
2 7 4 4
4 5 2 6 5
8과 0의 경우에는 1번 경우이므로 10과 15를 각각 더해주면 되고 1은 10과 15중 15가 더 크므로 15를 더해 주도록 한다.
7
10 15
18 16 15
2 7 4 4
4 5 2 6 5
2와 맨 끝의 4의 경우엔 1번이므로 18과 15를 각각 더해주고 7은 18과 16 중 18이 더 크므로 18을 더하고 4는 16과 15 중 16이 더 크므로 16을 더한다.
7
10 15
18 16 15
20 25 20 19
4 5 2 6 5
위와 같은 방법으로 계속 더해가면 된다.
7
10 15
18 16 15
20 25 20 19
24 30 27 26 24
이후 맨 마지막 인덱스 배열의 최댓값을 구하면 30을 얻을 수 있다.
1 2 3 4 5 6 7 8 9 10 | def solution(triangle): for i in range(1,len(triangle)): for j in range(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],triangle[i-1][j-1]) return max(triangle[-1]) | cs |
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 3. 입국 심사 (2) | 2019.03.01 |
|---|---|
| [Programmers]Lv 2. 타겟 넘버 (0) | 2019.02.28 |
| [Programmers]Lv 2. 카펫 (0) | 2019.02.26 |
| [Programmers]:Lv 3. 예산 (0) | 2019.02.25 |
| [Programmers]Lv 2. 구명 보트 (0) | 2019.02.24 |