Baekjoon1932: 정수 삼각형

Baekjoon1932: 정수 삼각형

정수 삼각형

한국어

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초 128 MB 52465 28961 21675 58.689%

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

풀이

Bottom → Top

삼각형에서 높이를 항으로 생각한다. 맨 윗줄은 1항 2번째 줄은 2항, 3번째 줄은 3항... n번째 줄은 n항이다

dp는 매 줄에서의 최대값을 기록한다. 각 항에서의 최대값을 기록할 수 있다.

→ 맨 위 꼭대기 7의 최대값은 7이며 dp[1][1]=7이라고 할 수 있다

→ 두번째 줄 3에서의 최대값은 이전항 7에서부터 왔으므로 dp[2][1] =10 이다

→ 두번째 줄 8에서의 최대값은 이전항 7에서부터 왔으므로 dp[2][2] =15 이다

→ 세번째 줄 1에서의 최대값은 dp[2][1]=10과 dp[2][2]=15중 더 큰 값을 가져온다. dp[3][2]=는 18+1 =19가 된다

※ 세번째 줄을 통해 dp[n][j]를 표현할 수 있다. dp[n][j] = Math.max( dp[n-1][j-1] , dp[n-1][j] )

※ 하지만 맨 끝에 있는 숫자들은 선택권이 없다. 아래 삼각형에서 2와 4는 이전 줄 맨 끝에서 이동한 결과이다.

현재줄에서 dp[n][j]는 다음의 규칙으로 기록된다

1) dp[n][j]가 줄에서 맨 처음에 있는 값일 때: dp[n][처음항] = dp[n-1][처음항] + 현재 숫자

2) dp[n][j]가 줄에서 맨 마지막에 있는 값일 때: dp[n][마지막항] = dp[n-1][마지막항] + 현재 숫자

3) 그 외 모든 dp[n][j]: Math.max( dp[n-1][j-1] , dp[n-1][j] ) + 현재 숫자

import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n =Integer.parseInt(st.nextToken()); int[][] triangle = new int[500][500]; //[500][500] 배열 생성 Integer[][] dp = new Integer[n][500]; //제한조건에서 n의 최대는 500이다 for(int i=0;i

from http://devyoseph.tistory.com/121 by ccl(A) rewrite - 2021-10-30 05:02:23