6
1 2
3 7 4
9 4 1 7
2 7 5 9 4
์ ํํ์ ๊ฐ์ด ์ผ๊ฐํ ๋ชจ์์ผ๋ก ๋ฐฐ์น๋ ์์ฐ์๋ค์ด ์์ต๋๋ค. ๋งจ ์์ ์ซ์์์ ์์ํด, ํ ๋ฒ์ ํ ์นธ์ฉ ์๋๋ก ๋ด๋ ค๊ฐ ๋งจ ์๋ ์ค๋ก ๋ด๋ ค๊ฐ๋ ๊ฒฝ๋ก๋ฅผ ๋ง๋ค๋ ค๊ณ ํฉ๋๋ค. ๊ฒฝ๋ก๋ ์๋ ์ค๋ก ๋ด๋ ค๊ฐ ๋๋ง๋ค ๋ฐ๋ก ์๋ ์ซ์, ํน์ ์ค๋ฅธ์ชฝ ์๋ ์ซ์๋ก ๋ด๋ ค๊ฐ ์ ์์ต๋๋ค. ์ด ๋ ๋ชจ๋ ๊ฒฝ๋ก ์ค ํฌํจ๋ ์ซ์์ ์ต๋ ํฉ์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์.
์ ๋ ฅ
์ ๋ ฅ์ ์ฒซ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ์ C(C <= 50)๊ฐ ์ฃผ์ด์ง๋๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ ์ค์๋ ์ผ๊ฐํ์ ํฌ๊ธฐ n(2 <= n <= 100)์ด ์ฃผ์ด์ง๊ณ , ๊ทธ ํ n์ค์๋ ๊ฐ 1๊ฐ~n๊ฐ์ ์ซ์๋ก ์ผ๊ฐํ ๊ฐ ๊ฐ๋ก์ค์ ์๋ ์ซ์๊ฐ ์ผ์ชฝ๋ถํฐ ์ฃผ์ด์ง๋๋ค. ๊ฐ ์ซ์๋ 1 ์ด์ 100000 ์ดํ์ ์์ฐ์์ ๋๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค ํ ์ค์ ์ต๋ ๊ฒฝ๋ก์ ์ซ์ ํฉ์ ์ถ๋ ฅํฉ๋๋ค.
๊ฐ ์นธ์ ์ ํ ์๋ ์ซ์๋งํผ ์ค๋ฅธ์ชฝ ๋๋ ์๋์ชฝ์ผ๋ก ์ด๋ํ ์ ์์ ๋ชฉ์ ์ง์ ๋์ฐฉํ๋ ๊ฒฝ๋ก์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฒ์ ์ฐพ๊ณ ์ถ๋ ฅ
๋ฉ๋ชจ์ด์ ์ด์ : ์ ์ฅํด๋๊ณ ์ฌ์ฉํ๊ธฐ (์ค๋ณต ์ฐ์ฐ ๊ฐ์)
1) ๋ฉ๋ชจ์ด์ ์ด์
int ret = cache[y][x];
if(ret != -1) return ret;
return ret = Math.max(path(y+1,x), path(y+1, x+1)) + triangle[y][x];
import java.util.Scanner;
public class DP_EX_3 {
static int n, triangle[][] = new int[100][100];
static int cache[][] = new int[100][100];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
while(tc > 0) {
n = sc.nextInt();
int size = 0;
for(int i=0; i<n; i++) {
size++;
for(int j=0; j<size; j++) {
triangle[i][j] = sc.nextInt();
cache[i][j] = -1;
}
}
System.out.println(path(0,0));
tc--;
}
}
static int path(int y, int x) {
if(y == n-1) return triangle[y][x];
int ret = cache[y][x];
if(ret != -1) return ret;
return ret = Math.max(path(y+1,x), path(y+1, x+1)) + triangle[y][x];
}
}
์ฑ ๋๋ก ํ์๋๋ฐ ์๊ฐ ์ด๊ณผ๋๋ ๊ฑฐ๋ .. ์ ๊ทธ๋ ์ง?