[백준 / JAVA] 9465번 스티커

이 글에는 백준 9465번 스티커 문제에 대한 풀이와 정답 코드(JAVA)가 있습니다.

 

문제

2n 개의 점수가 부여되어 있는 스티커를 구매한 상근이.

스티커를 선택하여 점수의 합이 최대가 되게 하고 스티커를 떼어내려고 하지만 해당 스티커를 선택하면 인접한 스티커는 사용할 수 없다.

1 ≤ n ≤ 100,000

0 ≤ 점수 ≤ 100

 

풀이

• DP를 이용하여 점화식을 세워서 풀이
• n = 1인 경우를 고려해야함

 

위의 표와 같이 스티커가 주어지면 아래와 같은 DP 배열을 통해서 최댓값을 구할 수 있습니다.

노란색으로 칠해진 곳의 스티커를 선택하면 최댓값의 점수를 구할 수 있습니다.

DP를 이용하여 최댓값을 구했을 때 가장 오른쪽에 위치한 점수 두개 중 최댓값을 최종 결과로 제출합니다.

 

각 칸마다 점수를 다르게 한 위의 예시를 통해 DP를 이해하게된다면 보다 쉬울것이라고 생각합니다.

 

//0열에는 자기자신이 최댓값이므로 저장
dp[0][0] = sticker[0][0];
dp[1][0] = sticker[1][0];

//1열은 자기자신과 인접하지 않은 0열의 값을 더한 것이 최댓값
dp[0][1] = dp[1][0] + sticker[0][1];
dp[1][1] = dp[0][0] + sticker[1][1];

 

 

2열부터는 3개를 비교해서 최댓값을 구합니다.

1. 자기자신 + 인접하지 않은 i-1열 값
2. 자기자신 + i-2열의 0행값
3. 자기자신 + i-2열의 1행값

i-2열은 0행, 1행 모두 인접하지 않으므로 이와 같이 비교할 수 있습니다.

 

//현재 위치의 최댓값은 
for (int i = 2; i < N; i++) {
	dp[0][i] = Math.max(dp[1][i - 1] + sticker[0][i], Math.max(dp[0][i - 2] + sticker[0][i], dp[1][i - 2] + sticker[0][i]));
	dp[1][i] = Math.max(dp[0][i - 1] + sticker[1][i], Math.max(dp[0][i - 2] + sticker[1][i], dp[1][i - 2] + sticker[1][i]));
}

 

또한 아래의 테스트 케이스와 같은 데이터가 추가됨에 따라 N=1인 경우에는 예외처리를 해주어야 합니다.

1
1
30
50
정답 : 50

if (N == 1) { // 데이터 추가에 따른 예외 처리
	System.out.println(Math.max(sticker[0][0], sticker[1][0]));
} else {//DP 행렬을 이용한 최댓값 처리}

 

 

전체 코드

import java.util.Scanner;

public class BOJ_9465_스티커_DP {
	static int T, N;
	static int[][] sticker;

	public static void main(String[] args) {
		Scanner scann = new Scanner(System.in);
		T = scann.nextInt();

		for (int tc = 0; tc < T; tc++) {
			N = scann.nextInt();

			sticker = new int[2][N];
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < N; j++) {
					sticker[i][j] = scann.nextInt();
				}
			} // end input

			if (N == 1) { // 데이터 추가에 따른 예외 처리
				System.out.println(Math.max(sticker[0][0], sticker[1][0]));
			} else {
				int[][] dp = new int[2][N];
				dp[0][0] = sticker[0][0];
				dp[1][0] = sticker[1][0];
				dp[0][1] = dp[1][0] + sticker[0][1];
				dp[1][1] = dp[0][0] + sticker[1][1];

				for (int i = 2; i < N; i++) {
					dp[0][i] = Math.max(dp[1][i - 1] + sticker[0][i],
							Math.max(dp[0][i - 2] + sticker[0][i], dp[1][i - 2] + sticker[0][i]));
					dp[1][i] = Math.max(dp[0][i - 1] + sticker[1][i],
							Math.max(dp[0][i - 2] + sticker[1][i], dp[1][i - 2] + sticker[1][i]));
				}

				System.out.println(Math.max(dp[0][N - 1], dp[1][N - 1]));
			}

		}
	}
}

 

9465번: 스티커

9465번: 스티커