๐ [๋ฐฑ์ค์๊ณ ๋ฆฌ์ฆ ํ์ด] Q.2096 ๋ด๋ ค๊ฐ๊ธฐ ๋ฌธ์ ํ์ด
๐ ๋ฌธ์
https://www.acmicpc.net/problem/2096
N์ค์ 0 ์ด์ 9 ์ดํ์ ์ซ์๊ฐ ์ธ ๊ฐ์ฉ ์ ํ ์๋ค. ๋ด๋ ค๊ฐ๊ธฐ ๊ฒ์์ ํ๊ณ ์๋๋ฐ, ์ด ๊ฒ์์ ์ฒซ ์ค์์ ์์ํด์ ๋ง์ง๋ง ์ค์์ ๋๋๊ฒ ๋๋ ๋์ด์ด๋ค.
๋จผ์ ์ฒ์์ ์ ํ ์๋ ์ธ ๊ฐ์ ์ซ์ ์ค์์ ํ๋๋ฅผ ๊ณจ๋ผ์ ์์ํ๊ฒ ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ค์ ์ค๋ก ๋ด๋ ค๊ฐ๋๋ฐ, ๋ค์ ์ค๋ก ๋ด๋ ค๊ฐ ๋์๋ ๋ค์๊ณผ ๊ฐ์ ์ ์ฝ ์กฐ๊ฑด์ด ์๋ค. ๋ฐ๋ก ์๋์ ์๋ก ๋์ด๊ฐ๊ฑฐ๋, ์๋๋ฉด ๋ฐ๋ก ์๋์ ์์ ๋ถ์ด ์๋ ์๋ก๋ง ์ด๋ํ ์ ์๋ค๋ ๊ฒ์ด๋ค. ์ด ์ ์ฝ ์กฐ๊ฑด์ ๊ทธ๋ฆผ์ผ๋ก ๋ํ๋ด์ด ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
๋ณํ๋ ํ์ฌ ์์น์ด๊ณ , ๊ทธ ์๋ซ ์ค์ ํ๋ ๋๊ทธ๋ผ๋ฏธ๋ ์๋ฃก์ด๊ฐ ๋ค์ ์ค๋ก ๋ด๋ ค๊ฐ ์ ์๋ ์์น์ด๋ฉฐ, ๋นจ๊ฐ ๊ฐ์ํ๋ ์๋ฃก์ด๊ฐ ๋ด๋ ค๊ฐ ์ ์๋ ์์น๊ฐ ๋๋ค. ์ซ์ํ๊ฐ ์ฃผ์ด์ ธ ์์ ๋, ์ป์ ์ ์๋ ์ต๋ ์ ์, ์ต์ ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ์๋ ์๋ฃก์ด๊ฐ ์์นํ ๊ณณ์ ์์ ํฉ์ด๋ค.
๐ ์ ๊ทผ๋ฒ
boj Q.2096 ๋ด๋ ค๊ฐ๊ธฐ ๋ฌธ์ ์ ๋๋ค.
๋ด๋ ค๊ฐ๊ธฐ ๊ฒ์์ ํตํด ์ต๋ ์ ์์ ์ต์ ์ ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค.
๋ฌธ์ ์์ ์ฃผ์ด์ง ์กฐ๊ฑด์ ์ ์ดํด๋ณด๋ฉด ๋์ ํ๋ก๊ทธ๋๋ฐ ๋ฐฉ์์ผ๋ก ํ์ด๊ฐ ๊ฐ๋ฅํฉ๋๋ค.
์ฒซ๋ฒ์งธ์์๋ ์ฒซ๋ฒ์งธ ๋๋ฒ์งธ๋ก ๋ด๋ ค๊ฐ ์ ์๊ณ
๋๋ฒ์งธ์์๋ ์ฒซ๋ฒ์งธ ๋๋ฒ์งธ ์ธ๋ฒ์งธ ๋ชจ๋ ๋ด๋ ค๊ฐ ์ ์๊ณ
์ธ๋ฒ์งธ์์๋ ๋๋ฒ์งธ ์ธ๋ฒ์งธ๋ก ๋ด๋ ค๊ฐ ์ ์์ต๋๋ค.
์ด ๊ท์น์ ์ ์๊ฐํด๋ณด๋ฉด ๋ค์๊ณผ ๊ท์น์ผ๋ก ๋ง๋ค์๋ ์์ต๋๋ค.
์ฒซ๋ฒ์งธ ์์น๋ก ๋ด๋ ค๊ฐ๋ ค๋ฉด ํ์ฌ ์์น๊ฐ ์ฒซ๋ฒ์งธ์ด๊ฑฐ๋ ๋๋ฒ์งธ์ฌ์ผํ๊ณ
๋๋ฒ์งธ ์์น๋ก ๋ด๋ ค๊ฐ๋ ค๋ฉด ํ์ฌ ์์น๊ฐ ์ฒซ๋ฒ์งธ์ด๊ฑฐ๋ ๋๋ฒ์งธ์ด๊ฑฐ๋ ์ธ๋ฒ์งธ์ฌ์ผํ๊ณ
์ธ๋ฒ์งธ ์์น๋ก ๋ด๋ ค๊ฐ๋ ค๋ฉด ํ์ฌ ์์น๊ฐ ๋๋ฒ์งธ์ด๊ฑฐ๋ ์ธ๋ฒ์งธ์ฌ์ผํฉ๋๋ค.
์ด๋ ๊ฒ ์๋ก์ด ๊ท์น์ ๋ง๋ค์ด ์ด์ฉํ๋ฉด (์ต๋ ์ ์ ๊ธฐ์ค)
๋ค์๊ณผ ๊ฐ์ ์ ํ์์ ๋์ถํ ์ ์์ต๋๋ค.
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();
}
}