백준_9465 스티커(자바) / DP

시간 & 메모리 제한

문제

입력 & 출력

- dp 의 값의 크기를 봤을 때, 100000이고 100씩을 반복한다 하더라도 최대 1,000,000 이므로 int로도 충분히 담을 수 있다.

 

DP를 이용한 문제풀이

package com.Back;

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

public class Back_9465 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		//테케 수 받기
		int testCase = Integer.parseInt(br.readLine());
		
		//테케 수 만큼 for문
		for (int tc = 0; tc < testCase; tc++) {
			int N = Integer.parseInt(br.readLine());
			
			//처음에는 N개로 했는데,두칸 이전의 칸을 설정하기 위해서 1칸을 늘림
			//아니면 두번째 칸까지 미리 계산을 해놔야 한다.
			int[][] map = new int[2][N+1];
			int[][] dp = new int[2][N+1];
			
			for (int i = 0; i < 2; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 1; j <= N; j++) {
					map[i][j]=Integer.parseInt(st.nextToken());
				}
			}
			
			//첫번째는 빈칸 두번째 라인 부터 dp의 값을 만들어 준다.
			dp[0][1] += map[0][1];
			dp[1][1] += map[1][1];
			
			// 위 아래로 나눠서 점화식을 만들어 
			for (int i = 2; i <= N; i++) {
				dp[0][i]=Math.max(dp[1][i-1], dp[1][i-2])+map[0][i];
				dp[1][i]=Math.max(dp[0][i-1], dp[0][i-2])+map[1][i];
			}
			sb.append(Math.max(dp[0][N], dp[1][N])+"\n");
		}
		System.out.println(sb);
	}
}

 

- 이 문제는 DP를 이용해서 푸는 문제였습니다.

 

- 이 문제에 대한 점화식에 대한 생각을 가진다면, 쉽게 푸실 수 있습니다.

 

점화식을 만드는 과정에서 문제에서 힌트를 얻을 수 있었습니다. 예시의 마지막에 보면 한칸을 뛰어서 선택하는 것이 더 큰 선택이였습니다.

 

임의로 0 0 을 만들어 놨습니다.

두번째 10과 50에서 dp를 고려 해보면, 10의 경우는 30과 0을 모두 고려해야 한다는 것입니다. 

 

예를 들어서 100이라는 입장에서 50이라는 위치의 dp와 130이라는 위치의 dp를 모두 고려해야 한다는 점입니다. 지그재그로만 구하면 안되는 이유를 확인할 수 있습니다.

50인 지점의 dp는 100이고 130이라는 지점의 dp는 130 입니다.

 

즉 100보다는 130이 더 크기 때문에 130인 두칸 전의 값을 선택할 수 있는 경우가 발생합니다.