[코딩테스트] 백준(BAEKJOON) - 연속합(Java, 1912번)

안녕하세요.

오늘 풀어볼 문제는 1912번 문제인 연속합이라는 문제입니다.

 

막판에 헷갈렸는데 그래도 어찌저찌 풀었네요...

남들은 다 쉽게풀었다는데

큰일났습니다 정말 ㅠㅠㅠ 알고리즘 실력이 올라가는건지 모르겠네요.. ㅠㅠ

 

그래도 꾸준히 하며 제 자신을 성장 시켜보겠습니다.

문제 만나보시죠~

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

즉 연속되는 합을 구해야되는 문제입니다.

다음은 제가 작성한 코드입니다.

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


//추후 다시 풀어볼 문제
public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		int count=Integer.parseInt(bf.readLine());
		String line=bf.readLine();
		
		String[] lineArray=line.split(" ");
		int max=0;
		int sum=0;
		for(int i=0;i<count;i++)
		{
			sum=sum+Integer.parseInt(lineArray[i]);
			if(max<sum)
				max=sum;	
			else if(sum<0)
				sum=0;			
				
		}
		if(max!=0)
			System.out.println(max);
		else
		{
			max=Integer.MIN_VALUE;
			for(int i=0;i<count;i++)
			{
				max=Math.max(max, Integer.parseInt(lineArray[i]));
			}
			System.out.println(max);
		}		
	}

}

나름 계속 DP를 생각하며 풀자고 햇지만 이렇게 됐네요~

계속더하면서 최대값을 갱신하되! 음수가 있다면 sum을 매섭게 0으로 초기화 해줬습니다.

sum이 음수인채로 계속 갖고있으면 다음수에 영향을 주기에 깔끔하게 초기화 후 다시 시작한다는 의미이기 때문이죠~

 

그렇게해서 최댓값을 구하면되겠습니다만!

여기서 문제는 바로 모든 수가 음수일 경우입니다. 저같이 풀면 음수일때0으로 초기화 하기에~

max값이 0이나오는 참사가 발생합니다.

 

그렇기에 밑에 부분처럼 max!=0이라는 부분을 줬습니다.

왜 근데 0이아닐때지?? 그러면 max가 >=0일경우도 되지 않나라고 생각이 들 수 있습니다.

 

여기서 생각하면

case 1 : 모든 배열이 양수일경우 ==> 0이 나올 수 없다.

case 2 : 모든 배열이 음수일경우 ==> 0이 역시 나올 수 없다 따라서 재 탐색필요

case 3 : 양수, 음수 배열이 합쳐질경우 ==> 여기서 충분히 최댓값이 0이 나올 수 있지 않나?라는 생각이 들기도 했지만 case에서 언급했듯 양수, 음수의 조합입니다. 그렇다면 여기서 max, 즉 최댓값은 0이아닌 양수가 나와야겠지요~

그렇기 때문에 max값이 0이아니면 재탐색 시켜주시면 되겠습니다.

 

이번문제는 여기서 간단하게 마무리하겠습니다.

 

감사합니다. :D