글 읽기 - 반례를 알고싶습니다.

dlgmlakd6503 1년 전 0

반례를 알 수 있을까요 ?

import java.io.*;
import java.util.*;

public class Main {
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.valueOf(br.readLine());
		if(n == 1) {
			System.out.println(Integer.parseInt(br.readLine()));
			return;
		}
		int[][] dp = new int[n][n];
		
		for(int i = 0; i < dp.length; i++) {
			for(int j = 0; j < dp[i].length; j++) {
				dp[i][j] = 0;
			}
		}
		
		for(int i = 0; i < n; i++) {
			String[] s = br.readLine().split(" ");
			for(int j = 0; j < s.length; j++) {
				dp[i][j] = Integer.valueOf(s[j]);
			}
		}
		
		dp[1][0] += dp[0][0];
		dp[1][1] += dp[0][0];
		
		for(int i = 2; i < dp.length; i++) {
			for(int j = 0; j < dp[i].length; j++) {
				if(j == 0) {
					dp[i][j] += dp[i-1][0];
				}else if(j == dp[i].length -1) {
					dp[i][j] += dp[i-1][dp[i].length -1];
				}else {
					if(dp[i-1][j-1] + dp[i][j] > dp[i-1][j] + dp[i][j]) {
						dp[i][j] += dp[i-1][j-1];
					}else {
						dp[i][j] += dp[i-1][j];
					}
				}
			}
		}
		System.out.println(Arrays.stream(dp[n-1]).max().getAsInt());
	}		
}

dlgmlakd6503 1년 전 0

해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 알고싶습니다.

dlgmlakd6503 1년 전 0

dlgmlakd6503 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말