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

+ Recent posts

티스토리툴바