๋ชฉ์ฐจ
๋ฌธ์
https://www.acmicpc.net/problem/1932
ํ์ด
์ผ๋จ ๊ฐ ํ์์ ์ต๋๊ฐ์ ์ ํํด์ ํ๋ฉด ์ ๋ต์ด ๋์ค๋์ง ํ์ธํด๋ณด์
7 -> 8 -> 1 -> 7 -> 5 = 28
์ ๋ต์ธ 30๋ณด๋ค ์๋ค. ์ด๋ ๊ฒ ํ๋ฉด ํ๋ฆฌ๊ฒ๋๋ค.
DP๋ฌธ์ ๋ ์ ํ์์ ์ธ์์ ํ์ด์ผํ๋ ๊ฒฝ์ฐ๊ฐ ๋ง๋ค.
๋ํ ์ด๋ ๊ฒ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ ํด์ "์ต์๊ฐ", "์ต๋๊ฐ"์ ์ฐพ๊ฒ๋๋ฉด ๊ฐ์ ๋์ ํ์ฌ ์ฒ๋ฆฌํด์ผํ๋ค.
์๋ ์ฌ์ง์ฒ๋ผ ์ผ๋จ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ ํ๊ณ , ์ ํ์์ ์ด๋์ด๋ธ๋ค.
์ฃผํฉ์ ๋ถ๋ถ์ 2๊ฐ์ง ๊ฐ์ ๊ฐ์ง ์ ์๋๋ฐ, ๋น๊ตํ์ฌ ์ต๋๊ฐ์ ์ ์ฅํ๋ค.
์ ํ์ (x, y)
A. [x][y] = [x-1][y-1] + [x][y]
B. [x][y] = [x-1][y] + [x][y]
1. x-1 < 0 ์ธ ๊ฒฝ์ฐ๋ ์ฐ์ฐ์ด ๋ถ๊ฐํ๋ค. (๋ฐฐ์ด ์ธ๋ฑ์ค๊ฐ -1์ด ๋๋๊น)
2. ๊ฐ ํ์ ๋งจ ์ฒซ๋ฒ์งธ ๊ฐ์ [x-1][y]๋ง ์ํํ๋ฉด๋๋ค.
3. ๊ฐ ํ์ ๋งจ ๋ง์ง๋ง ๊ฐ์ [x-1][y-1]๋ง ์ํํ๋ฉด๋๋ค.
์ ์ถ์ฝ๋
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] triangle = null;
static int sum = 0;
static int N = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
triangle = new int[N][N];
//์
๋ ฅ๋ฐ๊ธฐ
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int count = st.countTokens();
for (int j = 0; j < count; j++) {
triangle[i][j] = Integer.parseInt(st.nextToken());
process(i, j);
sum = Math.max(sum, triangle[i][j]);
}
//print();
}
System.out.println(sum);
}
private static void process(int i, int j) {
//System.out.println("("+i+", "+j+")");
if(i-1 < 0){
return;
}
int tempA = 0;
if(j-1 >= 0){
tempA = triangle[i-1][j-1] + triangle[i][j];
}
int tempB = triangle[i-1][j] + triangle[i][j];
triangle[i][j] = Math.max(tempA, tempB);
//sum = Math.max(sum, triangle[i][j]);
//N์ด 1์ผ๋ sum์ ๊ณ์ 0์ผ๋ก ๋์ฌ์๋ฐ์ ์๋ค. ๋ฐ๋ผ์ ์์ชฝ์ผ๋ก ์ฝ๋๋ฅผ ์ฎ๊ฒจ์ฃผ์ด์ผํ๋ค.
//(3, 0)์ธ ๊ฒฝ์ฐ tempB(2, 0)๋ง ๊ฐ์ด ํ ๋น๋๋ค.
//(3, 3)์ธ ๊ฒฝ์ฐ tempA(2, 2)์ tempB(2, 3)์ด ํ ๋น๋์ง๋ง tempB(2, 3)์ ์ด์ฐจํผ 0 ์ด๊ธฐ ๋๋ฌธ์ max๊ฐ์ธ tempA๊ฐ์ด ํ ๋น๋๋ค.
}
private static void print() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(triangle[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
'๐ฏ Coding Test' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 9095๋ฒ 1, 2, 3 ๋ํ๊ธฐ ์๋ฐ DP (0) | 2022.03.25 |
---|---|
[๋ฐฑ์ค] 1074๋ฒ Z ์๋ฐ (๋ถํ ์ ๋ณต) (0) | 2022.02.24 |
[๋ฐฑ์ค] 2630๋ฒ ์์ข ์ด ๋ง๋ค๊ธฐ ์๋ฐ (๋ถํ ์ ๋ณต) (0) | 2022.02.22 |
[๋ฐฑ์ค] 1012 ์ ๊ธฐ๋๋ฐฐ์ถ ์๋ฐ BFS, DFS (0) | 2022.02.21 |
[๋ฐฑ์ค] 1697 ์จ๋ฐ๊ผญ์ง 1์ฐจ์ BFS (0) | 2022.02.12 |