[백준] JAVA 자바 : 스티커 (9465번)

---

어려운 줄 알았는데 막상 생각을 좀 해보니 생각보다 쉬웠던 문제다.

가로의 길이를 N으로 두고 1부터 올려가면서 점화식을 구하면 된다.

N이 N+1이 될 때 가질 수 있는 최대 가치는,

N에서 윗줄(아랫줄)을 선택했다면 N+1번째에는 아랫줄(윗줄)을 선택하는 것 혹은 N-1번째에서 큰 값중 N+1번째의 위아래를 더하는 값 중 하나로 결정된다.

 

솔직히 이것도 글로만 보면 이해가 안 돼서...
코드로 보고 이해하심 됩니다ㅋㅋ

 

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

public class Sticker {

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

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

        int T = stoi(br.readLine());
        for (int k=0; k<T; k++) {

            int n = stoi(br.readLine());
            int[][] price = new int[2][n];

            for (int i=0; i<2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j=0; j<n; j++) {
                    price[i][j] = stoi(st.nextToken());
                }
            }

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

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

 

로그인

 

 

작성일자: 2024-01-18