[백준] 9465번 : 스티커 / java - DP 문제

 

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

9465번: 스티커

 

[ 코드 ]

 

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

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

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

        for (int tc=1; tc<=T; tc++) {
            int N = Integer.parseInt(br.readLine());

            int[][] 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());
                }
            }

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

 

 

[ 실패 코드 ]

 

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

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

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

        for (int tc=1; tc<=T; tc++) {
            int N = Integer.parseInt(br.readLine());

            int[][] sticker = new int[2][N];

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

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

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

 

 

점화식을 세우고 결과값이 들어맞아서 너무 기뻤지만 알고보니 이것은 반쪽짜리 점화식입니다!
칸이 홀수개일때 가능한 점화식. 반쪽짜리 점화식이었다! 미리 두칸을 계산해버리는 식입니다.

 

1. 지그재그로 한칸씩 두개
2. 건너서 한개

 

둘 중 하나의 경우의 수를 체크한건데, 한번에 두 칸씩 하다보니 짝수칸일때는 계산이 안된다.

 

 

 

※ 오늘의 교훈

DP 문제 감이 잡혀가고, 점화식을 직접 세워가는 것만으로도 잘했다. 더 간단한 점화식을 생각해보자!

 

 

 

참고 :
https://fbtmdwhd33.tistory.com/76