[JAVA] 1912 - 연속합 🩶2 : 정답을 보면 간단해보여도, 빠르게 떠올리지 못한 문제 + 백준 섭종 발표 다음날...(개가 짖어도 기차는 간다!)

제목으로

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

1912번: 연속합

n개의 정수로 이루어진 임의의 수열에서, 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 정답으로 출력하면 되는 문제이다.

본문으로

딱 문제를 읽자마자 for문으로 하나씩 다 구하면 되는 거 아니야? 했다가 바로 n <= 100,000인 거 보고 음.. 이거 시간복잡도 걸리는 문제군 싶었다..

그래서 합의 최대니까 구간합을 구해놓으면 뭔가 쉽게 되지 않을까? 라고 생각하고 로직 작성에 들어갔다.(비극의 시작..) 그래서 아래와 같은 구간합을 미리 구해놓는 식으로 시간복잡도를 줄여보려 했는데... 뭔가 자꾸 안되었다.

pSum[i] = pSum[i - 1] + arr[i];

 

결국 이 문제는 모든 연속 구간 중 최대합을 찾아야 했다. 즉 pSum으로 하면 결국

• 모든 구간을 다 비교하거나
• 최소 prefix를 관리하거나

이런 식으로 생각이 한 번 더 꼬이는 문제가 생겼다.

---

꽤 오래 생각했는데.. 확실한 아이디어가 안떠올라서 질문 게시판을 봤다.. 사실 거의 정답에 가까운 아이디어를 봐버렸다. 그곳에서 얻은 아이디어는

현재까지의 구간의 합이 양수라면 구간을 이어가고 음수라면 구간을 끊고 다시 0부터 시작하며 매번 최댓값을 갱신하면 되지 않겠는가?  이다. 그렇다면 아래와 같이 매우 간단하게 로직을 작성할 수 있다.

public class Main {

    static int n, ret;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        ret = -1004; // 숫자 범위 -1000 ~ 1000
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            sum += num;
            ret = Math.max(ret, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        System.out.println(ret);
    }
}

마무리하며

이전 상태의 최적값을 이용해서 현재상태의 최적값을 만드는 형태니 어찌보면 DP문제였다고도 할 수 있겠다!! 어색하다!!!

 

+ 추가적으로 어제 밤 백준 서버의 종료 소식이 전해졌다... 그럼에도 문제푸는 습관은 버리지 않으려고 한다. 나름 재밌기도 하고(?) PS는 이제 뭐 필요없다.. 어쩌고저쩌고 말이 많지만, 이런 문제 꾸준히 푸는 삶이 만족스럽고 내 개인적으로도 뿌듯한 느낌이 든다. PS가 메인이 되면 안되겠지만, 긍정적인 영향을 주는 문제푸는 습관은 삶의 깊은 곳까지 들어와버려서 이제는 포기할 수 없다!!

 

백준이 되살아나기를 빌며.. 백준이 섭종하는 그날까지 꾸준히 문제를 풀어보자!!.. 섭종하면 어느 플랫폼에서 풀지도 찾아봐야겠다..

#WE_WANT_BOJ_BACK