BEAKJOON / 백준 - JAVA 9465번 스티커

2024.08.26기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 조건으로 스티커를 붙힐 때 점수를 합산 해, 가장 높은 점수를 출력하는 문제입니다.

 

이 문제는 붙이는 방식에서 조건을 찾는것이 핵심이라고 생각합니다.

v 체크된 스티커를 붙힐 때, 참고 해야하는 스티커는 총 2개로 0줄이면 1줄, 1줄이면 0줄에서 앞쪽 과 2번째 앞쪽을 참고 해 큰 값을 가지고 가는 조건입니다.

dp로 접근하게 된다면

이렇게 뒤에 있는 2개의 칸을 참조하도록 하는 것입니다.

 

1. 입력받은 스티커 점수를 배열에 저장합니다.

n = Integer.parseInt(br.readLine()); // 한 줄의 스티커 개수

sticker = new int[2][n + 1];
for (int i = 0; i < 2; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 1; j <= n; j++) {
        sticker[i][j] = Integer.parseInt(st.nextToken());
    }
}

 

2. 저장된 점수로 dp배열을 생성합니다.

dp = new int[2][n + 1];

// 첫 번째 칸의 dp를 설정해줍니다.
dp[0][1] = sticker[0][1];
dp[1][1] = sticker[1][1];

// 2번째 칸부터 뒤에 칸을 확인하면서 더 큰 값과 같이 더 해 줍니다.
for (int i = 2; i <= n; i++) {
    dp[0][i] = Math.max(dp[1][i - 2], dp[1][i - 1]) + sticker[0][i];
    dp[1][i] = Math.max(dp[0][i - 2], dp[0][i - 1]) + sticker[1][i];
}

반복문을 돌 때 현재 인덱스에서 반대편 (0 -> 1, 1 -> 0) 줄에 뒷 인덱스와 뒷 2번째 인덱스 중 큰 값과 현재 자신의 점수를 더해 dp를 채워가도록 합니다.

 

3. 마지막에 저장된 dp 합계로 더 큰 값을 출력하게 됩니다.

// 마지막에 계산된 2줄 중 더 큰 값을 출력합니다.
sb.append(dp[0][n] > dp[1][n] ? dp[0][n] : dp[1][n]).append("\n");

 

 

 

코드

package Main;

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
		
		int n;
		int[][] sticker, dp;
		StringTokenizer st;
		
		while (t-- > 0) {
			n = Integer.parseInt(br.readLine()); // 한 줄의 스티커 개수
			
			sticker = new int[2][n + 1];
			for (int i = 0; i < 2; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 1; j <= n; j++) {
					sticker[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			dp = new int[2][n + 1];
			
			// 첫 번째 칸의 dp를 설정해줍니다.
			dp[0][1] = sticker[0][1];
			dp[1][1] = sticker[1][1];
			
			// 2번째 칸부터 뒤에 칸을 확인하면서 더 큰 값과 같이 더 해 줍니다.
			for (int i = 2; i <= n; i++) {
				dp[0][i] = Math.max(dp[1][i - 2], dp[1][i - 1]) + sticker[0][i];
				dp[1][i] = Math.max(dp[0][i - 2], dp[0][i - 1]) + sticker[1][i];
			}
			
			// 마지막에 계산된 2줄 중 더 큰 값을 출력합니다.
			sb.append(dp[0][n] > dp[1][n] ? dp[0][n] : dp[1][n]).append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}