문제

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
        int a[][] = new int[n+1][n+1];
		int d[][] = new int[n+1][n+1];
				
		for(int i=1; i<=n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1; j<=i; j++) {
				a[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				d[i][j] = Math.max(d[i-1][j-1], d[i-1][j]) + a[i][j];
			}
		}
		int ans=0;
		//마지막층 각각에 최댓값을 가지고 있어서 가장 큰 값 찾아준다.
		for(int i=1; i<=n; i++) {
			if(ans < d[n][i]) ans = d[n][i]; 
		}
		
		System.out.println(ans);
	}
}

a						d
[0, 0, 0, 0, 0, 0]		[0, 0, 0, 0, 0, 0]
[0, 7, 0, 0, 0, 0]		[0, 7, 0, 0, 0, 0]
[0, 3, 8, 0, 0, 0]		[0, 10, 15, 0, 0, 0]
[0, 8, 1, 0, 0, 0]		[0, 18, 16, 15, 0, 0]
[0, 2, 7, 4, 4, 0]		[0, 20, 25, 20, 19, 0]
[0, 4, 5, 2, 6, 5]		[0, 24, 30, 27, 26, 24]

• 비용 문제, 또는 숫자의 누적 문제는 문제에서 주어진 입력과 동일하게 배열을 하나 만들어 해당하는 지점까지의 결과를 저장해 나가면서 풀면 된다는 것을 알게 됨.

1932번 풀이