[java]스티커 - 백준9465

문제

• 스티커(백준9465)

풀이

문제 해석을 하자면,

• 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

풀이

• 브루트포스로 구현하기도 복잡하며, N 범위가 너무 크기 때문에 동적프로그래밍으로 접근한다.

• DP 점화식 -> 아래 그림 참고

  • dp[0][i] = Math.max(dp[1][i - 1] + inArr[0][i], dp[1][i - 2] + inArr[0][i]);
    dp[1][i] = Math.max(dp[0][i - 1] + inArr[1][i], dp[0][i - 2] + inArr[1][i]);
    

점화식 구하는 과정

코드

public static void main(String[] args) throws IOException {
    StringBuilder sb =new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    for (int t = 0; t < T; t++) {
        int N = Integer.parseInt(br.readLine());
        int[][] inArr = new int[2][N + 1];
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            inArr[0][i] = Integer.parseInt(stk.nextToken());
        }
        stk = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            inArr[1][i] = Integer.parseInt(stk.nextToken());
        }
        //run
        //dp init
        int[][] dp = new int[2][N + 1];
        dp[0][0] = inArr[0][0];
        dp[1][0] = inArr[1][0];
        dp[0][1] = inArr[1][0]+inArr[0][1];
        dp[1][1] = inArr[0][0]+inArr[1][1];
        //dp
        for (int i = 2; i < N; i++) {
            dp[0][i] = Math.max(dp[1][i - 1] + inArr[0][i], dp[1][i - 2] + inArr[0][i]);
            dp[1][i] = Math.max(dp[0][i - 1] + inArr[1][i], dp[0][i - 2] + inArr[1][i]);
        }
        //output
        sb.append(Math.max(dp[0][N - 1], dp[1][N - 1])).append("\n");
    }
    System.out.println(sb);
}

느낀점

생략