글 읽기 - max값 설정에 대한 질문!

win198978 4년 전 0

안녕하세요. 항상 친절한 답변에 감사드립니다.

다름이 아니라 이 문제에 마지막에서 계속 틀렸습니다..를 받고 혹시나 이건가 싶어 고쳐본 것이 하나 있었는데요,

대체 왜 이것 때문에 틀렸을까.. 하는 궁금증이 풀리질 않아 질문글에 글을 올려봅니다.(주석에 표기해놓았습니다)

고수분들의 고견 부탁드립니다.

감사합니다!!

import java.util.Scanner;

public class Main {
    private static int N = 0;
    private static int[] sequence = null;

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        N = scn.nextInt(); scn.nextLine();
        sequence = new int[N];
        for (int i = 0; i < N; i++) {
            sequence[i] = scn.nextInt();
        }
        // maxValue를 Integer.MIN_VALUE()로 두면 틀렸습니다.. 로 나옵니다..
        int maxValue = sequence[0];
        int[] dp = new int[N];
        dp[0] = sequence[0];
        for (int i = 1; i < N; i++) {
            int tmp = dp[i - 1] + sequence[i];
            int value = (tmp < sequence[i])? sequence[i] : tmp;
            dp[i] = value;
            if(maxValue < value){
                maxValue = value;
            }
        }
        if(N == 1){
            maxValue = dp[0];
        }
        System.out.println(maxValue);
        scn.close();
    }
}

vota12 4년 전 1

이유는 반례가 있기때문입니다.

15번째 줄의 int maxValue = sequence[0]; 이 아닌 Integer.MIN_VALUE() 로 두고

-100 -200

이걸 돌리시면 -200이 나오게 될 겁니다. 답은 당연히 -100입니다.

위의 경우처럼 입력하면 for문 내부에서 tmp = -300이 되서, int value에 sequence[1]값인 -200이 들어가게 되네요.

그런데 지금 maxValue를 정수중에 제일 작은 값으로 줬으니 당연히 -200이 더 큰값으로 인식되어 닶이 -200으로 나오는 것이구요.

기존의 maxValue = sequence[0] 으로 줬을때는 sequence[0]의 값인 -100이 더 크기 때문에 넘어가게됩니다.

아마 질문자님이 maxValue를 Integer.MIN_VALUE 로 주신 이유가 음수가 연속으로 나올때를 처리하기 위해서 이신거 같은데,

굳이 Integer.MIN_VALUE를 쓰고 싶으시면 간단하게

for(int i=0;i<N;i++) {

if(maxValue<dp[i])

maxValue = dp[i];

}

같은 코드를 추가하셔서 dp[] 값들 중 가장 큰값이 출력되게 하여 위와같은 반례를 막으시면 좋을거 같네요.

win198978 4년 전 1

아하... 제가 짠 소스의 경우 시퀀스의 첫 번째 수를 고려를 안 한 게 되는군요..

감사합니다!!

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

문제

문제

출처

ICPC

max값 설정에 대한 질문!

win198978 4년 전 0

vota12 4년 전 1

win198978 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말