[BAEKJOON] 1932 정수 삼각형

문제 요악

• 알고리즘 분류: 동적 계획법
• 난이도: Silver1
• 문제 요약
  • 위에서 아래로 내려올때  아래층 대각선 값중 하나씩 더해서 내간다.
  • 끝까지 내려갔을때 최대 값을 구해라.
• 사이트 주소: https://www.acmicpc.net/problem/1932

1912번: 연속합

문제 풀이

동적 계획법 관련 내용은 아래 사이트에 참조 하면된다.

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 나무위키

문제 접근 방법

 동적계획법은 규칙, 패턴만 알면 코드는 작성하는것은 쉽다. 하지만 규칙, 패턴을 찾기가 힘들어서 문제 이지만.....

7
3	8
8	1	0
2	7	4	4
4	5	2	6	5

 삼각 형을 위에 표 처럼 나타낼수가 있다.

아래에서 아니라 아래층이 위층을 비교해서 저장하면 구현하기가 쉽다. 하지만 양끝은 조건문을 달아야 되서 불편하다 그래서 0번째 인덱스와 맨끝에 인덱스를 추가 를해서 for문으로 1분터 구한다면 아래 표처럼 나올 수 있다.

0	1	2	3	4	5
0	7	0
0	3	8	0
0	8	1	0	0
0	2	7	4	4	0
0	4	5	2	6	5

맨끝은 뒤에 0을 추가 할 필요가 없다.

0	1	2	3	4	5
0	7	0
0	3 + max(0, 7)	8 + max(7, 0)	0

맨 위를 보면 7라는 숫자라 하나라서 각각 더해주면된다.

그 다음줄을 보면

0	10	15	0
0	8 + max(0, 10)	1 + max(10, 15)	0 + max(15, 0)	0

2번 째 인덱스를 보면 10, 15 중 큰것만 더해서 저장 하면된다. 여기서 규칙을 보면 (x, y)번째 인덱스는 (x-1, y-1) 과 (x - 1, y)중 가장 큰값을 더하면 된다는 것을 표에서 확인 할수 있다. 이 방식으로 풀면

결과는 밑에 표처럼 나온다.

0	1	2	3	4	5
0	7	0
0	10	15	0
0	18	16	15	0
0	20	25	20	19	0
0	24	30	27	26	24

 이중 가장 큰값은 30으로 나오고 노란색으로 표시한것은 이동한 경로이다.

 

Code

Python

n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]

for i in range(n-1):
    triangle[i-1].append(0)
    triangle[i-1].insert(0, 0)
    for j in range(i+1):
        triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j+1])
        
print(max(triangle[-1]))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] array = new int[n][n+1];
		StringTokenizer st;
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j <= i; j++ ) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i = 1; i < n; i++) {
			array[i][0] += array[i-1][0]; 
			for(int j = 1; j <= i; j++) {
				array[i][j] += Math.max(array[i-1][j-1], array[i-1][j]);
			}
		}
		System.out.println(Arrays.stream(array[n-1]).max().getAsInt());
	}
			
}