백준 BOJ 9465 스티커 [자바]

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

9465번: 스티커

 

문제 분석

2*n개의 스티커가 있음.

하나의 스티커를 쓰면, 그 스티커와 변을 맞대는 스티커는 못 씀.

각 스티커마다 가치가 다를 때, 최대 사용 가능한 가치는?

 

 

입력조건

테스트 케이스 수 N

각 테스트 케이스 마다{

  배열의 크기 n

  배열 두줄에 걸쳐 나열됨.

}

 

풀이과정

그냥 점화식으로 앞에서부터 올라가면서 구함.

 

dp문제를 몇일 연속으로 푸니 더 쓸만한 말이 없군요...

 

전체 코드

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

public class 백준9465_스티커 {
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			int n = Integer.parseInt(br.readLine());
			int[][] sti = new int[3][n];
			for(int i = 0; i < 2; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0; j < n; j++) {
					sti[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			// 입력받기 끝.
			
			for(int i = 1; i < n; i++) {
				for(int j = 0; j < 3; j++) {
					sti[j][i] += Math.max(sti[(j+1)%3][i-1], sti[(j+2)%3][i-1]);		
				}
			}
			// sum 구하기 끝.
			int max = Math.max(sti[0][n-1],  Math.max(sti[1][n-1], sti[2][n-1]));
			sb.append(max + "\n");
		}
		System.out.println(sb);
	}
}