본문 바로가기
알고리즘(Java)/다이나믹 프로그래밍(동적계획법)

백준 1932 숫자삼각형

Gongdel 2017. 12. 12. 09:10

문제

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

위 그림은 크기가 5인 숫자 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 숫자는 모두 정수이며, 범위는 0 이상 99 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1≤n≤500)이 주어지고, 둘째 줄부터 n+1줄까지 숫자 삼각형이 주어진다.

출력

첫째 줄에는 최대가 되는 합을 출력한다.

예제 입력 

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

예제 출력 

30

힌트

출처

Olympiad > International Olympiad in Informatics > IOI 1994 1번

알고리즘 분류

 

문제를 풀 때 삼각형 수의 각 자리의 배열 위치를 그려보고 규칙을 찾아서 풀면 됩니다.

 

예)        0 0

        1 0   1 1

     2 0 , 2 1, 2 2

   3 0, 3 1, 3 2, 3 3

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int [][] dp = new int[n][n];
		
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j <= i; j++){
				dp[i][j] = sc.nextInt();
			}
		}
		
		for(int i = 1; i < n; i++){
			for(int j = 0; j <= i; j++){
				//왼쪽 사이드의 규칙
				if(j == 0){
					dp[i][j] += dp[i - 1][j];
				//오른쪽 사이드의 규칙	
				}else if(i == j){
					dp[i][j] += dp[i -1][j -1];
				}else{
					dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j]);
				}
			}
		}
		
		int max = 0;
		for(int i = 0; i < n; i++){
			if(max < dp[n - 1][i]){
				max = dp[n - 1][i];
			}
		}
		System.out.println(max);
	}
	
	public static int max(int a, int b){
		if(a > b){
			return a;
		}else{
			return b;
		}
	}
}

'알고리즘(Java) > 다이나믹 프로그래밍(동적계획법)' 카테고리의 다른 글

백준 1463 1로 만들기  (0) 2017.12.14
백준 2579 계단오르기  (0) 2017.12.13
백준 1149 RGB  (0) 2017.12.11

'알고리즘(Java)/다이나믹 프로그래밍(동적계획법)' Related Articles

티스토리툴바