https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
문제 해결을 위한 과정
전형적인 다이나믹 프로그래밍 문제였습니다. 이 문제의 경우 숫자의 배열이 삼각형이라는 점이 존재하는데 이를 다음의 표처럼 입력받은 부분을 제외한 영역을 0을 채워주면 보다 쉽게 해결할 수 있습니다. 이 과정을 통해 0번째 열의 경우는 바로 위에 존재하는 숫자를 더해주면 되고 그 외의 경우는 위 행의 좌측 열 값과 위 행의 동일 열 값의 max값을 더해주는 과정을 반복해주면 쉽게 해결할 수 있습니다. 이를 점화식으로 표현하면 다음과 같습니다.
array[i][j] += max(array[i-1][j-1], array[i-1][j])
(단 열이 0번째가 아닌 경우)
1. 입력받은 곳을 제외하고 0으로 채운 상태
| 7 | 0 | 0 | 0 | 0 |
| 3 | 8 | 0 | 0 | 0 |
| 8 | 1 | 0 | 0 | 0 |
| 2 | 7 | 4 | 4 | 0 |
| 4 | 5 | 2 | 6 | 5 |
2. 적색 숫자는 0번째 열 이므로 위의 7을 그대로 더함, 청색 숫자는 좌측 위의 7과 위의 0중 최댓값인 7을 더함
| 7 | 0 | 0 | 0 | 0 |
| 10 | 15 | 0 | 0 | 0 |
| 8 | 1 | 0 | 0 | 0 |
| 2 | 7 | 4 | 4 | 0 |
| 4 | 5 | 2 | 6 | 5 |
3. 적색 숫자는 0번째 열 이므로 위의 10을 그대로 더함. 청색 숫자는 좌측 위의 숫자와 위의 숫자의 최댓값인 각각 15, 15를 더함
| 7 | 0 | 0 | 0 | 0 |
| 10 | 15 | 0 | 0 | 0 |
| 18 | 16 | 15 | 0 | 0 |
| 2 | 7 | 4 | 4 | 0 |
| 4 | 5 | 2 | 6 | 5 |
4. 적색 숫자는 0번째 열 이므로 위의 18을 그대로 더함, 청색 숫자는 좌측 위의 숫자와 위의 숫자의 최댓값인 각각 18, 16, 15를 더함
| 7 | 0 | 0 | 0 | 0 |
| 10 | 15 | 0 | 0 | 0 |
| 18 | 16 | 15 | 0 | 0 |
| 20 | 25 | 20 | 19 | 0 |
| 4 | 5 | 2 | 6 | 5 |
5. 적색 숫자는 0번째 열 이므로 위의 20을 그대로 더함. 청색 숫자는 좌측 위의 숫자와 위의 숫자의 최댓값인 각각 25, 25, 20, 19를 더함
| 7 | 0 | 0 | 0 | 0 |
| 10 | 15 | 0 | 0 | 0 |
| 18 | 16 | 15 | 0 | 0 |
| 20 | 25 | 20 | 19 | 0 |
| 24 | 30 | 27 | 26 | 24 |
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
n = int(input())
array = [[0] * n for _ in range(n)] # 0으로 전부 채워진 이차원 배열 생성
for i in range(n):
input_data = list(map(int, input().split()))
for j in range(len(input_data)):
array[i][j] = input_data[j]
for i in range(1, n):
for j in range(n):
if j == 0: # 0번째 열 인경우
array[i][j] += array[i-1][j]
else: # 그 외의
array[i][j] += max(array[i-1][j-1], array[i-1][j])
answer = 0
for i in range(n):
answer = max(answer, array[n-1][i])
print(answer)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 18353: 병사 배치하기(Python) (0) | 2020.12.21 |
|---|---|
| 백준 알고리즘 14501: 퇴사 (Python) (1) | 2020.12.19 |
| 백준 알고리즘 2110: 공유기 설치 (Python) (0) | 2020.12.18 |
| 백준 알고리즘 18310: 안테나(Python) (2) | 2020.12.10 |
| 백준 알고리즘 16234: 국영수(Python) (0) | 2020.12.09 |