๐Ÿ“– [๋ฐฑ์ค€์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€์ด] Q.2096 ๋‚ด๋ ค๊ฐ€๊ธฐ ๋ฌธ์ œ ํ’€์ด

๐Ÿ“– ๋ฌธ์ œ

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

N์ค„์— 0 ์ด์ƒ 9 ์ดํ•˜์˜ ์ˆซ์ž๊ฐ€ ์„ธ ๊ฐœ์”ฉ ์ ํ˜€ ์žˆ๋‹ค. ๋‚ด๋ ค๊ฐ€๊ธฐ ๊ฒŒ์ž„์„ ํ•˜๊ณ  ์žˆ๋Š”๋ฐ, ์ด ๊ฒŒ์ž„์€ ์ฒซ ์ค„์—์„œ ์‹œ์ž‘ํ•ด์„œ ๋งˆ์ง€๋ง‰ ์ค„์—์„œ ๋๋‚˜๊ฒŒ ๋˜๋Š” ๋†€์ด์ด๋‹ค.

๋จผ์ € ์ฒ˜์Œ์— ์ ํ˜€ ์žˆ๋Š” ์„ธ ๊ฐœ์˜ ์ˆซ์ž ์ค‘์—์„œ ํ•˜๋‚˜๋ฅผ ๊ณจ๋ผ์„œ ์‹œ์ž‘ํ•˜๊ฒŒ ๋œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‹ค์Œ ์ค„๋กœ ๋‚ด๋ ค๊ฐ€๋Š”๋ฐ, ๋‹ค์Œ ์ค„๋กœ ๋‚ด๋ ค๊ฐˆ ๋•Œ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ œ์•ฝ ์กฐ๊ฑด์ด ์žˆ๋‹ค. ๋ฐ”๋กœ ์•„๋ž˜์˜ ์ˆ˜๋กœ ๋„˜์–ด๊ฐ€๊ฑฐ๋‚˜, ์•„๋‹ˆ๋ฉด ๋ฐ”๋กœ ์•„๋ž˜์˜ ์ˆ˜์™€ ๋ถ™์–ด ์žˆ๋Š” ์ˆ˜๋กœ๋งŒ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ์ด ์ œ์•ฝ ์กฐ๊ฑด์„ ๊ทธ๋ฆผ์œผ๋กœ ๋‚˜ํƒ€๋‚ด์–ด ๋ณด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

down

๋ณ„ํ‘œ๋Š” ํ˜„์žฌ ์œ„์น˜์ด๊ณ , ๊ทธ ์•„๋žซ ์ค„์˜ ํŒŒ๋ž€ ๋™๊ทธ๋ผ๋ฏธ๋Š” ์›๋ฃก์ด๊ฐ€ ๋‹ค์Œ ์ค„๋กœ ๋‚ด๋ ค๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์œ„์น˜์ด๋ฉฐ, ๋นจ๊ฐ„ ๊ฐ€์œ„ํ‘œ๋Š” ์›๋ฃก์ด๊ฐ€ ๋‚ด๋ ค๊ฐˆ ์ˆ˜ ์—†๋Š” ์œ„์น˜๊ฐ€ ๋œ๋‹ค. ์ˆซ์žํ‘œ๊ฐ€ ์ฃผ์–ด์ ธ ์žˆ์„ ๋•Œ, ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ ์ˆ˜, ์ตœ์†Œ ์ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ ์ˆ˜๋Š” ์›๋ฃก์ด๊ฐ€ ์œ„์น˜ํ•œ ๊ณณ์˜ ์ˆ˜์˜ ํ•ฉ์ด๋‹ค.

๐Ÿ” ์ ‘๊ทผ๋ฒ•

boj Q.2096 ๋‚ด๋ ค๊ฐ€๊ธฐ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๋‚ด๋ ค๊ฐ€๊ธฐ ๊ฒŒ์ž„์„ ํ†ตํ•ด ์ตœ๋Œ€ ์ ์ˆ˜์™€ ์ตœ์†Œ ์ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๋ฌธ์ œ์—์„œ ์ฃผ์–ด์ง„ ์กฐ๊ฑด์„ ์ž˜ ์‚ดํŽด๋ณด๋ฉด ๋™์ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋ฐฉ์‹์œผ๋กœ ํ’€์ด๊ฐ€ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

์ฒซ๋ฒˆ์งธ์—์„œ๋Š” ์ฒซ๋ฒˆ์งธ ๋‘๋ฒˆ์งธ๋กœ ๋‚ด๋ ค๊ฐˆ ์ˆ˜ ์žˆ๊ณ 

๋‘๋ฒˆ์งธ์—์„œ๋Š” ์ฒซ๋ฒˆ์งธ ๋‘๋ฒˆ์งธ ์„ธ๋ฒˆ์งธ ๋ชจ๋‘ ๋‚ด๋ ค๊ฐˆ ์ˆ˜ ์žˆ๊ณ 

์„ธ๋ฒˆ์งธ์—์„œ๋Š” ๋‘๋ฒˆ์งธ ์„ธ๋ฒˆ์งธ๋กœ ๋‚ด๋ ค๊ฐˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ด ๊ทœ์น™์„ ์ž˜ ์ƒ๊ฐํ•ด๋ณด๋ฉด ๋‹ค์Œ๊ณผ ๊ทœ์น™์œผ๋กœ ๋งŒ๋“ค์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.

์ฒซ๋ฒˆ์งธ ์œ„์น˜๋กœ ๋‚ด๋ ค๊ฐ€๋ ค๋ฉด ํ˜„์žฌ ์œ„์น˜๊ฐ€ ์ฒซ๋ฒˆ์งธ์ด๊ฑฐ๋‚˜ ๋‘๋ฒˆ์งธ์—ฌ์•ผํ•˜๊ณ 

๋‘๋ฒˆ์งธ ์œ„์น˜๋กœ ๋‚ด๋ ค๊ฐ€๋ ค๋ฉด ํ˜„์žฌ ์œ„์น˜๊ฐ€ ์ฒซ๋ฒˆ์งธ์ด๊ฑฐ๋‚˜ ๋‘๋ฒˆ์งธ์ด๊ฑฐ๋‚˜ ์„ธ๋ฒˆ์งธ์—ฌ์•ผํ•˜๊ณ 

์„ธ๋ฒˆ์งธ ์œ„์น˜๋กœ ๋‚ด๋ ค๊ฐ€๋ ค๋ฉด ํ˜„์žฌ ์œ„์น˜๊ฐ€ ๋‘๋ฒˆ์งธ์ด๊ฑฐ๋‚˜ ์„ธ๋ฒˆ์งธ์—ฌ์•ผํ•ฉ๋‹ˆ๋‹ค.

example

์ด๋ ‡๊ฒŒ ์ƒˆ๋กœ์šด ๊ทœ์น™์„ ๋งŒ๋“ค์–ด ์ด์šฉํ•˜๋ฉด (์ตœ๋Œ€ ์ ์ˆ˜ ๊ธฐ์ค€)

๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ ํ™”์‹์„ ๋„์ถœํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

1๋ฒˆ์งธ๋กœ ๋‚ด๋ ค๊ฐ€๊ธฐ ์ตœ๋Œ€ ์ ์ˆ˜ = ์ฒซ๋ฒˆ์งธ ์œ„์น˜ ์ถœ๋ฐœ or ๋‘๋ฒˆ์งธ ์œ„์น˜ ์ถœ๋ฐœ 
d[i][1] = max (d[i-1][1] + score[i][1], d[i-1][2] + score[i][1])

2๋ฒˆ์งธ๋กœ ๋‚ด๋ ค๊ฐ€๊ธฐ ์ตœ๋Œ€ ์ ์ˆ˜ = ์ฒซ๋ฒˆ์งธ ์œ„์น˜ ์ถœ๋ฐœ or ๋‘๋ฒˆ์งธ ์œ„์น˜ ์ถœ๋ฐœ or ์„ธ๋ฒˆ์งธ ์œ„์น˜ ์ถœ๋ฐœ
d[i][2] = max(d[i-1][1]+score[i][2], d[i-1][2]+score[i][2] , d[i-1][3]+score[i][2] )

3๋ฒˆ์งธ๋กœ ๋‚ด๋ ค๊ฐ€๊ธฐ ์ตœ๋Œ€ ์ ์ˆ˜ = ๋‘๋ฒˆ์งธ ์œ„์น˜ ์ถœ๋ฐœ or ์„ธ๋ฒˆ์งธ ์œ„์น˜ ์ถœ๋ฐœ
d[i][3] = max(d[i-1][2]+score[i][3], d[i-1][3]+score[i][3]  ); 

์ด๋ฅผ ์ด์šฉํ•ด ์ตœ๋Œ€ ์ ์ˆ˜๋ฅผ ๋™์ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ๊ณ 

๋ฐ˜๋Œ€๋กœ ์ตœ์†Œ ์ ์ˆ˜ ๋˜ํ•œ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๐Ÿ’ป ์ฝ”๋“œ

package problem.dynamic;

import java.io.*;

public class Main_2096 {
    static int n;
    static int[][] d;
    static int [][] score;

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        maxSolve();
        minSolve();
        bw.flush();
        bw.close();
    }

    public static void maxSolve() {
        for(int i=1; i<=n; i++){
            d[i][1] = Math.max(d[i][1], d[i-1][1]+score[i][1] );
            d[i][1] = Math.max(d[i][1], d[i-1][2]+score[i][1] );

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

            d[i][3] = Math.max(d[i][3], d[i-1][2]+score[i][3] );
            d[i][3] = Math.max(d[i][3], d[i-1][3]+score[i][3] );
        }
        int max = Math.max(d[n][1],d[n][2]);
        max = Math.max(max,d[n][3]);
        System.out.println(max);
    }

    public static void minSolve() {
        for(int i=1; i<=n; i++){
            d[i][1] = Math.min(d[i][1], d[i-1][1]+score[i][1] );
            d[i][1] = Math.min(d[i][1], d[i-1][2]+score[i][1] );

            d[i][2] = Math.min(d[i][2], d[i-1][1]+score[i][2] );
            d[i][2] = Math.min(d[i][2], d[i-1][2]+score[i][2] );
            d[i][2] = Math.min(d[i][2], d[i-1][3]+score[i][2] );

            d[i][3] = Math.min(d[i][3], d[i-1][2]+score[i][3] );
            d[i][3] = Math.min(d[i][3], d[i-1][3]+score[i][3] );
        }
        int min = Math.min(d[n][1],d[n][2]);
        min = Math.min(min,d[n][3]);
        System.out.println(min);
    }


    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        d = new int[n + 1][4];
        score = new int[n+1][4];
        for(int i=1; i<=n; i++){
            String temp[] = br.readLine().split(" ");
            for(int j=1; j<=3; j++){
                score[i][j] = Integer.parseInt(temp[j-1]);
            }
        }
        br.close();
    }
}

Written on May 23, 2021