[백준] 9465번 : 스티커

문제

 

 

접근 방식

각 스티커를 고른 상태 안고른 상태로 백트래킹으로 탐색하면

주어진 입력의 최대 범위로는 시간초과가 발생해 완탐으로 풀 수 없는 문제라

DP를 이용해 풀어야 한다.

 

DP로는 O(N)에 풀 수 있는데 우선 DP 테이블부터 만들어보자.

10 30 10 50 100 20 40
20 40 30 50 60 20 80

 

위와 같은 입력이 주어졌다고 가정하면

0		40	30	100	180	130	230
0	10	50	60	130	210	210	270
0	20	50	80	110	190	230	290
0		40	50	100	120	150	290

 

위와 같은 표가 만들어지고 2, 3번째 행이 DP 테이블에 저장될 값들이다.

 

우선 각 줄의 스티커가 선택될 수 있는 경우는

현재 줄의 이전 스티커를 사용하지 않았거나

현재 줄의 이전 스티커보다 현재 스티커를 사용하는게 더 효율적인 경우다.

 

즉, 현재까지 고른 스티커의 누적값을 DP[i][j]라 했을 때

(DP[다른 행의][이전 스티커 = j - 1] + 현재 스티커 값) == 현재 줄의 이전 스티커를 사용하지 않은 경우

(DP[다른 행의][2번째 전 스티커 = j - 2] + 현재 스티커 값) == 현재 스티커가 더 효율적인 경우

중에서 가장 큰 값으로 테이블을 채워주면 되고

테이블을 다 채운 후에 마지막 값 중 가장 큰 것이 정답이 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine()), n;

		while (t-- > 0) {
			n = Integer.parseInt(br.readLine());

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

			for (int i = 0; i < 2; i++) {
				st = new StringTokenizer(br.readLine());

				for (int j = 1; j <= n; j++) {
					stickers[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			dp[0][1] = stickers[0][1];
			dp[1][1] = stickers[1][1];

			for (int i = 2; i <= n; i++) {
				int s1 = stickers[0][i];
				int s2 = stickers[1][i];
				dp[0][i] = Math.max(dp[1][i-1] + s1, dp[1][i-2] + s1);
				dp[1][i] = Math.max(dp[0][i-1] + s2, dp[0][i-2] + s2);
			}

			sb.append(Math.max(dp[0][n], dp[1][n])).append("\n");
		}

		System.out.println(sb);
	}
}