글 읽기 - accept된 답인데 자체 로직에서 문제가 있는 것으로 생각됩니다.

arisu 3년 전 0

점화식을 정의할 때

dp[i] : 첫번째 ~ i번째 수까지의 연속합

dp2[i] : i번째 ~ 마지막 수까지의 연속합

으로 정의했는데, 마지막 루프에 주석으로 달아 놓았는데

n번째 수를 제외한 경우를 고려하지 않았는데 정답으로 인정되는 것 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		// read input
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s = bf.readLine();
		int n = Integer.parseInt(s);
		
		// convert string array to an integer array
		String[] numbersAsString = bf.readLine().split(" ");
		int[] numbers = new int[numbersAsString.length+1];
		for (int j=1; j<=numbersAsString.length; j++) {
			numbers[j] = Integer.parseInt(numbersAsString[j-1]); 
		}

		int[] dp = new int[n+1]; // consecutive sum from first ~ i-th number
		int[] dp2 = new int[n+1]; // consecutive sum from i-th ~ last number
		// if you want to get consecutive sum excluding k-th number, just add dp[k-1] + dp2[k+1].
		
		dp[1] = numbers[1];		
		for (int i=2; i<=n; i++) {
			dp[i] = numbers[i];
			dp[i] = Math.max(dp[i-1] + numbers[i], dp[i]);
		}
        
		dp2[n] = numbers[n];
		for (int j=n-1; j>=1; j--) {
			dp2[j] = numbers[j];
			dp2[j] = Math.max(dp2[j], dp2[j+1] + numbers[j]);
		}
		
		// for the case when you include all numbers (described in the problem)
		int answer = dp[1];
		for (int i=2; i<=n; i++) {
			answer = Math.max(dp[i], answer);
		}
		
		// for the case when you exclude single number, from 1 ~ last number
		for (int k=1; k<=n-1; k++) {
			answer = Math.max(answer, dp[k-1] + dp2[k+1]);
			//System.out.println("excluding "+k+"-th number : " + numbers[k] +", left sum : " + dp[k-1] +", right sum : "+ dp2[k+1]);
		}
		
		// dp[0] + dp2[2] = exclude 1-th number
		// dp[1] + dp2[3] = exclude 2-th number
		// ...
		// dp[n-2] + dp2[n] = exclude (n-1)th number
		// then where is the case that we exclude n-th number? 
		// also, I did not assign any value to dp[0], but dp[0] is referred at the first loop.
		
		System.out.println(answer);
		
		bf.close();	
		return;
	}

}

slah007 3년 전 0

41번줄을 읽어보세요

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

문제

문제

출처

ICPC

accept된 답인데 자체 로직에서 문제가 있는 것으로 생각됩니다.

arisu 3년 전 0

slah007 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말