백준 1932번 : 정수 삼각형

https://www.acmicpc.net/problem/1932

JAVA를 통해 풀었고, DP 개념을 아예 몰랐는데 이번 기회로 처음,, 대충,, 맛만,,? 향만,,? 알게 되는 계기가 되었다..

 

(1) DFS방식으로 풀어서 시간초과가 난 코드.

import java.util.Scanner;

public class Main {
	public static int N, ans = 0;
	public static int[][] map;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		map = new int[N+1][N+1];
		//i는 층 수, j는 해당 층의 방 번호 - 편의상 맨 꼭대기를 1층으로하고 맨아랫층을 N층으로 함
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < i; j++) {
				map[i][j]=sc.nextInt();
			}
		}
		
		dfs(1,0,0);
		System.out.println(ans);
	}
	
	public static void dfs(int row, int col, int sum) {
		
		//1.종료조건 - N층인가? 최대인가?
		if(row>N) {
			ans = Math.max(sum, ans);
			return;
		}
		//2.방향탐색
		//자기 기준으로 층은 한층올리고 방은 자신,자신+1만 돌면 됨
		for (int i = col; i <= col+1; i++) {
			
			dfs(row+1,i,sum+map[row][col]);
		}
	}

}

(2) DP를 이용해서 푼 코드

문제에서 최댓값을 구해나가는 방식은 선택한 값에서 왼쪽 대각선 아래 또는 오른쪽 대각선 아래로만 이동할 수 있다고 하였다. 이 말을 살짝 바꿔보면, 선택한 값을 만드는 방법은 왼쪽 위의 값 또는 오른쪽 위의 값 중 큰 값을 고른 뒤 더해 나온 값이란 얘기다. 출처 - https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220789773974&proxyReferer=https%3A%2F%2Fwww.google.com%2F

그리하여 하나 하나 시작점이 되었을때 밑에서 위로 계산하는 방식을 이용했다.

EX) 

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

 

2층의 1번째방인 3의 경우 1층의 1번과 0번방밖에 갈 수 없다. (왼쪽 위와 오른쪽위를 봐야하니까)

(나 자신+왼쪽 위의 방 숫자 합) 과 (나 자신+오른쪽 위의 방 숫자 합)을 구해서 더 큰쪽의 수를 내 방에 저장해둔다.

 

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

4층의 2번째방인 7의 경우 (7+8)과 (7+1) 했을때 7+8=15로 더 커서 저 값이 4층 2번째방에 저장되도록한다..

 

그렇게 나올 수 있는 가장 큰 값들만을 저장해오며 내려가다가 끝에 도달하면 max값을 추린다.

import java.util.Scanner;

public class Main {
	public static int N, ans = 0;
	public static int[][] map;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		map = new int[N+1][N+1];
		//i는 층 수, j는 해당 층의 방 번호 - 편의상 맨 꼭대기를 1층으로하고 맨아랫층을 N층으로 함
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= i; j++) {
				map[i][j]=sc.nextInt();
				
				map[i][j] = map[i-1][j-1] > map[i-1][j] ? map[i-1][j-1]+map[i][j] : map[i-1][j]+map[i][j];
				ans = Math.max(ans, map[i][j]);
			}
		}
	
		System.out.println(ans);
    }

}