πŸ“– [λ°±μ€€μ•Œκ³ λ¦¬μ¦˜ 풀이] Q.9465 μŠ€ν‹°μ»€ 문제 풀이 - java

πŸ“– 문제

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

πŸ” 접근법

Q.9465 μŠ€ν‹°μ»€ λ¬Έμ œμž…λ‹ˆλ‹€.

2n개의 μŠ€ν‹°μ»€κ°€ μ£Όμ–΄μ§‘λ‹ˆλ‹€. 각 μŠ€ν‹°μ»€ λ§ˆλ‹€ μ μˆ˜κ°€ λΆ€μ—¬λ˜μ–΄ μ£Όμ–΄μ§€λŠ”λ°

μŠ€ν‹°μ»€ ν•œ μž₯을 λ–Όλ©΄ ν•΄λ‹Ή μŠ€ν‹°μ»€μ™€ 변을 κ³΅μœ ν•˜λŠ” μŠ€ν‹°μ»€λ“€μ„ λ–Όμ–΄λ‚Ό 수 μ—†κ²Œ λ©λ‹ˆλ‹€.

μ΄λ•Œ μŠ€ν‹°μ»€λ₯Ό λ–Όμ–΄λ‚΄μ–΄ κ°€μž₯ λ†’κ²Œ 받을 수 μžˆλŠ” 점수λ₯Ό κ΅¬ν•˜λŠ” 것이 이 문제의 λ‹΅μž…λ‹ˆλ‹€.

동적 ν”„λ‘œκ·Έλž˜λ°μ„ 톡해 풀이가 κ°€λŠ₯ν•©λ‹ˆλ‹€.

μ„Έκ°€μ§€μ˜ κ²½μš°κ°€ μžˆμŠ΅λ‹ˆλ‹€.

ν˜„μž¬ μŠ€ν‹°μ»€λ₯Ό 떼지 μ•ŠλŠ” κ²½μš°μ—λŠ” λ‹€μŒ 칸의 μŠ€ν‹°μ»€λ₯Ό 떼지 μ•Šκ±°λ‚˜ μœ— λΆ€λΆ„μ΄λ‚˜ μ•„λž« 뢀뢄을 λ—„ 수 μžˆμŠ΅λ‹ˆλ‹€.

ν˜„μž¬ μŠ€ν‹°μ»€μ˜ μœ— 뢀뢄을 λ—„ κ²½μš°μ—λŠ” λ‹€μŒ 칸의 μŠ€ν‹°μ»€λ₯Ό 떼지 μ•Šκ±°λ‚˜ μ•„λž« λΆ€λΆ„λ§Œμ„ λ—„ 수 μžˆμŠ΅λ‹ˆλ‹€.

ν˜„μž¬ μŠ€ν‹°μ»€μ˜ μ•„λž˜ 뢀뢄을 λ—„ κ²½μš°μ—λŠ” λ‹€μŒ 칸의 μŠ€ν‹°μ»€λ₯Ό 떼지 μ•Šκ±°λ‚˜ μœ— λΆ€λΆ„λ§Œμ„ λ—„ 수 μžˆμŠ΅λ‹ˆλ‹€.

이 세가지 경우λ₯Ό μ΄μš©ν•˜μ—¬ 점화식을 ꡬ할 수 μžˆμŠ΅λ‹ˆλ‹€.

   d[0][i] += Math.max(d[1][i - 1], d[2][i - 1]);
   d[1][i] += Math.max(d[0][i - 1], d[2][i-1]) + sticker[1][i];
   d[2][i] += Math.max(d[0][i - 1], d[1][i-1]) + sticker[2][i];

μœ„μ˜ 점화식듀을 μ΄μš©ν•˜μ—¬ 동적 ν”„λ‘œκ·Έλž˜λ° λ°©μ‹μœΌλ‘œ

nμ—΄κΉŒμ§€μ˜ λ–Όμ–΄λ‚΄λŠ” μ΅œλŒ€ μ μˆ˜λ“€μ„ κ΅¬ν•˜μ—¬

μ΅œμ’… λ§ˆμ§€λ§‰ nμ—΄μ—μ„œ 떼지 μ•Šκ±°λ‚˜ μœ— λΆ€λΆ„μ΄λ‚˜ μ•„λž« 뢀뢄을 λ—€ κ°’ 쀑

κ°€μž₯ 큰 μ μˆ˜κ°€ μ •λ‹΅μž…λ‹ˆλ‹€.

πŸ’» μ½”λ“œ


package problem.dynamic;
import java.io.*;

public class Main_9465 {
    static int n;
    static int t;
    static int[][] d;
    static int sticker[][];
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();
        input();
        System.out.println(sb.toString());
        bw.flush();
        bw.close();
    }
    public static void solve() {
        d = new int[3][n+1];
        for (int i = 1; i <= n; i++) {
            d[0][i] += Math.max(d[1][i - 1], d[2][i - 1]);
            d[1][i] += Math.max(d[0][i - 1], d[2][i-1]) + sticker[1][i];
            d[2][i] += Math.max(d[0][i - 1], d[1][i-1]) + sticker[2][i];
        }
        int result = Math.max(d[0][n],d[1][n]);
        result = Math.max(result,d[2][n]);
        sb.append(result+"\n");
    }

    public static void input () throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        for(int i=0; i<t; i++){
            n = Integer.parseInt(br.readLine());
            sticker = new int[3][n+1];
            for(int j=1; j<=2; j++){
                String[] in = br.readLine().split(" ");
                for(int k=1; k<in.length+1; k++){
                    sticker[j][k] = Integer.parseInt(in[k-1]);
                }
            }
            solve();
        }

        br.close();
    }
}


Written on April 7, 2021