백준 9465 - java 스티커(동적계획법)

문제, 입출력, 테스트 케이스

 

 

 

<문제 풀이/접근과정>
1. 손으로 그려가며 가능한 조합이 어떻게 되는 지 확인
O X O            
X O X  또는
O X O
X X O  뿐이라는 것을 확인
2. 앞의 결과가 뒤에도 영향을 미친다는 것을 인식
3. DP인 것을 어렴풋이 느낌
4. 점화식을 세워보았음
dp[0][n] = max(arr[0][n] + dp[1][n-1], arr[0][n] + dp[1][n-2])
dp[1][n] = max(arr[1][n] + dp[0][n-1], arr[1][n] + dp[0][n-2])
5. 결국 답은 dp값을 구한 후 Max값을 출력하는 것임 
6. 이 생각까지 다다르는 데 약 20분이 걸리고 코드 작성은 10분 가량 걸린 것으로 추정

왜 이렇게 차이가 날까?

해당 문제를 풀고 제출한 후 속도가 시간이 단순 System.out.println과 StringBuilder 중 String Builder가 느리길래 이번기회에 제대로 짚고 넘어가고자 찾아 보았다. 그래도 776 vs 900의 차이는 좀 너무한 거 같아서 더 돌려보니 서버 상황에 따라 달라졌을 것이라는 짐작을 할 수 있었다.

 

https://velog.io/@heoseungyeon/StringBuilder%EC%99%80-StringBuffer%EB%8A%94-%EB%AC%B4%EC%8A%A8-%EC%B0%A8%EC%9D%B4%EA%B0%80-%EC%9E%88%EB%8A%94%EA%B0%80

StringBuilder와 StringBuffer는 무슨 차이가 있는가?

https://mygumi.tistory.com/83

StringBuilder vs System.out.println :: 마이구미

 

<소스코드>

package 동적계획법_DP;

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

public class Boj_9465_스티커 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// dp[0][n] = max(arr[0][n] + dp[1][n-1], arr[0][n] + dp[1][n-2])
		// dp[1][n] = max(arr[1][n] + dp[0][n-1], arr[1][n] + dp[0][n-2])
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < T; i++) {
			int n = Integer.parseInt(br.readLine());
			int arr[][] = new int[2][n+2];
			int dp[][] = new int[2][n+2];
			for (int j = 0; j <= 1 ; j++) {
				StringTokenizer stz =new StringTokenizer(br.readLine());
				for (int k = 2; k < n+2; k++) {
					arr[j][k] = Integer.parseInt(stz.nextToken());
				}
			}
			int answer = 0;
			for (int j = 2; j < n+2; j++) {
				for (int k = 0; k <= 1; k++) {
					if(k == 0) {
						dp[0][j] = Math.max(arr[1][j] + dp[1][j-1], arr[1][j] + dp[1][j-2]);
						
					}else if(k == 1) {
						dp[1][j] = Math.max(arr[0][j] + dp[0][j-1], arr[0][j] + dp[0][j-2]);
					}
					answer = Math.max(dp[0][j], dp[1][j]);
				}
			}
			
			sb.append(answer).append("\n");
		}
		sb.setLength(sb.length()-1);
		
		System.out.println(sb.toString());
		
	}
}