[백준 9465번] 스티커 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

이번 문제는 DP를 이용하여 풀어보았습니다.

 

N이 1인 경우를 생각해 보도록 하겠습니다. N이 1인 경우 선택한 스티커의 값이 최댓값이 됩니다.

 

위쪽을 선택한 경우 아래쪽 스티커를 사용하지 못하고 아래쪽 스티커를 사용한 경우 위쪽 스티커를 사용하지 못하기 때문입니다.

 

아래 표 처럼 스티커 점수가 있다면 DP[0][1] = 50이 되며 DP[1][1] = 30이 됩니다. 추후 계산을 위해 Index는 1부터 시작하도록 하겠습니다. 

50

30

 

그럼 N이 2인 경우를 생각해 보겠습니다.

 

N이 2인 경우는 첫번째 선택의 대각선에 있는 스티커까지 선택이 가능합니다.

50	10
30	50

그렇다면 DP[0][2]는 40이 되며 DP[1][2]는 100이 될 것입니다.

 

이번에는 N이 3인 경우를 생각해 보겠습니다.

 

N이 3인 경우는 선택한 스티커의 왼쪽과 위쪽 또는 아래쪽 스티커를 선택할 수 없습니다.

 

만약 100 점수의 스티커를 사용한다면 선택 가능한 스티커는 50-50-100과 30-100이 될 것입니다.

 

위에 말한 50-50의 경우 이전 N이 2인 경우에서 구한 DP[1][2]의 값이 선택 가능한 최대의 값의 스티커입니다.

 

30 또한 DP[1][1]에 선택 가능한 최대의 값의 스티커 점수가 있습니다.

 

그럼 DP[0][3]의 값은 Max(DP[1][2], DP[1][1])이 될 것입니다.

50	10	100
30	50	70

 

위 과정을 점화식으로 만들면 N이 2 이상인 경우 아래와 같이 점화식이 만들어집니다.

DP[0][N] = Max(DP[1][N-1], DP[1][N-2])

DP[1][N] = Max(DP[0][N-1], DP[0][N-2])

 

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stringTokenizerIndex0;
StringTokenizer stringTokenizerIndex1;

int testCase = Integer.parseInt(br.readLine());

for(int i=0; i<testCase; i++){
	int num = Integer.parseInt(br.readLine());

	stringTokenizerIndex0 = new StringTokenizer(br.readLine());
	stringTokenizerIndex1 = new StringTokenizer(br.readLine());

	long[][] dp = new long[2][num+1];

	dp[0][1] = Long.parseLong(stringTokenizerIndex0.nextToken());
	dp[1][1] = Long.parseLong(stringTokenizerIndex1.nextToken());

	for(int j=2; j<=num; j++){
		dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + Long.parseLong(stringTokenizerIndex0.nextToken());
		dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + Long.parseLong(stringTokenizerIndex1.nextToken());
	}

	bw.write(Math.max(dp[0][num], dp[1][num]) + "\n");
	bw.flush();
}