백준 1806 자바 - 부분합 (BOJ 1806 JAVA)

문제 : boj1806

 

 

1. 틀린 방법

※ 제가 틀린 방법에 대해 써둔 것으로, 해설만 보고 싶다면 2번부터 보시면 됩니다.

  덱에 모든 값들을 담으면서 그 합을 따로 계산한다. 그럼 일단 그 합은 최대치로 나올 수 있는 합이 될 것이다. 그 합이 S보다 작다면 0을 출력하고, 그렇지 않다면 합이 S보다 작아질 때 까지 덱의 시작부분과 끝부분을 각각 peek 해봐서 둘 중 작은 값을 덱에서 빼버린다. 이렇게 하면 그리디하게 답을 구할수 있을줄 알았다. 예를들어 S가 5일 때 다음과 같이 수행한다.

이렇게 짠 코드는 다음과 같다.

 

※ 틀린 코드임

...
		int n = nextInt();
        int s = nextInt();
        int sum = 0;

        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            int cur = nextInt();
            sum += cur;
            dq.add(cur);
        }

        if (sum < s) {
            System.out.println(0);
            return;
        }

        while (!dq.isEmpty()) {
            int st = dq.peekFirst();
            int ed = dq.peekLast();
            int pop = st>ed?dq.pollLast():dq.pollFirst();
            if (sum-pop < s) break;
            sum-=pop;
            n--;
        }
        System.out.println(n);
...

 

 

  그럴듯해 보였으나, 틀렸고 다시 생각해보니 문제는 시작 부분과 끝 부분의 값이 동일할 경우 사실 양측이 동일한 값이 나오지 않을때까지 더 살펴봐야 한다는 점이었다(동일한 것 중 뭘 제거하냐에 따라 이후에 제거할 수 있는게 다름). 그렇다고 동일한 숫자가 나올 때 마다 동일한 숫자가 아닐 때 까지 서로 빼거나 탐색하자니 10만개짜리에 전부 '1'만 입력으로 들어오는 그런 테스트케이스에 대해 유효한 시간 내에 통과할 수 없을 거라 생각했다. 그럼 기본 로직은 그대로 가져오고(그리디), 반대로 수행하기로 했다.

 

 

 

2. 풀이

  '1'의 틀린 방법과 마찬가지로 그리디로 풀었다. 다만 '1'의 과정을 반대방향으로 할 것이므로 빈 덱에서 시작한다. 그리디 규칙은 다음과 같다.

 

A. 아직 합친 값(이하 SUM)이 S보다 낮다면 덱의 끝부분에 계속해서 입력을 받는다.

B. SUM이 S보다 높다면 덱의 시작 부분을 poll 한다.

 

위 둘을 반복하면서 중간중간 SUM이 S보다 높을 때 덱의 size 중 작은걸 기록해두면 그게 답이다. 종료 규칙은 덱이 비거나, n개를 모두 입력받은 상태에서 한번 더 SUM이 S보다 작아지는 경우이다.

 

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken())-1;
        int s = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(Integer.parseInt(st.nextToken()));
        int sum = dq.peekLast();
        int answer = Integer.MAX_VALUE;
        while (!dq.isEmpty()) {
            if (sum >= s) {
                answer = Math.min(answer, dq.size());
                sum -= dq.pollFirst();
                continue;
            }
            if (n == 0) break;
            n--;
            dq.addLast(Integer.parseInt(st.nextToken()));
            sum += dq.peekLast();
        }

        System.out.println(answer == Integer.MAX_VALUE ? 0 : answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}