[BackJoon] 백준 9465번 _ 스티커 for JAVA

 

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

9465번: 스티커

 

 

문제

 

 

---

 

처음에는 문제 접근을 백트래킹으로 했다.

 

 

그런데 n값이 10만까지인데 재귀를 빠져나올 조건이 딱히 안보였음. 

 

 

실컷 보다가 dp같아서 다른사람 풀이 참고했다.

 

 

풀이

 

예를 들어

저기에 있는 50은 무조건 스티커를 뜯는다고 하자.

 

그러면

 

 

저 파란색인 50과 70을 뜯었을 때 최대가 되도록 해야한다.

 

노란색의 오른쪽 10과 아래 30은 못 뜯는게 자명한데, 저 파란색 두 군데만 신경쓰는 이유는

 

 

100같은 경우 노란색에서 바로 100을 뜯는 것 보다 50 -> 파란색 50 -> 100을 뜯는게 더 효율적이기 때문이다.

 

 

이렇게!

 

그래서 대각선 50과 그 옆 70 중에서 큰 값을 선택하면서 그 자리에서 최선의 선택을 하면 된다.

 

 

이를 코드로 나타낼 때에는 현재 선택된 자리는 무조건 뜯는다고 가정하고, 이전에 무엇을 뜯었어야 가장 큰 값이 나오는지 확인하면 된다.

 

 

긍까

 

이전꺼 확인

 

이렇게 이전 대각선꺼를 확인해서 최적의 선택(둘 중 큰 값 선택)을 하면 된다.

 

 

 

 

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int tc=1; tc<=T; tc++) {
			int n = Integer.parseInt(br.readLine());
			int[][] score = new int[2][n+1];
			
			for(int i=0; i<2; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=1; j<=n; j++) {
					score[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			/* */
			int[][] dp = new int[2][n+1];
			dp[0][1] = score[0][1]; // [0][0] = 0이므로, 스티커는 1부터 표시한다.
			dp[1][1] = score[1][1];
			
			for(int i=2; i<=n; i++) {
				dp[0][i] = Math.max(dp[1][i-2], dp[1][i-1]) + score[0][i];
				dp[1][i] = Math.max(dp[0][i-2], dp[0][i-1]) + score[1][i];
			}
			
			sb.append(Math.max(dp[0][n], dp[1][n])).append('\n');
		}	
		System.out.println(sb.toString());
	}
}

 

 

성능

 

 

 

아~ dp 어렵다!

 

근데 이해하니까 재밌는듯.... 꼭 다시 풀어봐야지

 

 

dp를 부숴볼까......