boj)1932 - 정수 삼각형
2020. 9. 19. 17:08ㆍPS/boj
import java.io.*;
import java.util.StringTokenizer;
public class boj_1932 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static long[][] dp;
static int[][] val; // 0 ~ 9999
static int n; // 1 ~ 500
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
dp = new long[n+1][n+1];
val = new int[n+1][n+1];
// 맨 위가 1층 , 맨 아래가 n층
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= i; j++) {
val[i][j] = Integer.parseInt(st.nextToken());
dp[i][j] = val[i][j];
}
}
// n-1층부터 1층까지 구해가야함
for (int i = n-1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
dp[i][j] += Math.max(dp[i+1][j], dp[i+1][j+1]);
}
}
// 1층까지올라온 최댓값
System.out.println(dp[1][1]);
}
}
- 제일 아래층부터 올라가는 식으로 찾았음
- 초기 dp 에는 val값을 그대로 넣고, 제일 아래의 윗층 n-1층 부터 dp 시작
- i-1 층의 왼쪽 j와 오른쪽 j+1 중 큰것을 dp에 + 하는식으로 더하는 식으로 올라감
- 결국 최상단부인 [1][1] 에는 최댓값이 들어옴
'PS > boj' 카테고리의 다른 글
boj)11722 - 가장 긴 감소하는 부분 수열 (0) | 2020.09.20 |
---|---|
boj)11055 - 가장 큰 증가 부분 수열 (0) | 2020.09.19 |
boj)2156 - 포도주 시식 (0) | 2020.09.19 |
boj)9465 - 스티커 (0) | 2020.09.19 |
boj)11057 - 오르막수 (0) | 2020.09.19 |