[백준] 1806 : 부분합

문제 출처 : https://www.acmicpc.net/problem/1806

소요 시간 : 시도(40m) + 풀이(30m)

---

문제

---

시도

 

문제를 제대로 이해하지 않고 '그냥 투 포인터 쓰면 되겠지' 하면서 정렬하기 시작하면서 꼬이기 시작했고, 결국 40분을 온전히 낭비하고 장렬히 실패했다.

 

아래는 문제가 뭔지도 모르고 바보 같이 작성한 코드다.

// n (수열 요소 범위) : 1 ~ 10,000
// N (수열 길이) : 10 ~ 100,000
// S (목표 합) : 1 ~ 100,000,000

import java.io.*;
import java.util.*;

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        
        int sum = 0;
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i];
            
            // 단일 요소만으로 목표 합 S를 충족할 시 개수 1 출력
            if (arr[i] == S) {
               System.out.println(1);
               return;
            }
        }
        
        // 목표 합 S 모든 요소 총합보다 크다면 불가능(0) 출력
        if (S > sum) {
            System.out.println(0);
            return;
        }
        
        Arrays.sort(arr);
        
        int left = 0, right = N-1;
        while (left < right) {
            int num = arr[left] + arr[right];
            
            if (num == S) {
                System.out.println(2);
                return;
            }
            else if (num < S) left++;
            else if (num > S) right--;
        }
    }
}

---

풀이

 

바보 같은 시도로 문제를 실패한 뒤, 문제의 해결 방법을 찾기 위해 다른 사람의 풀이를 참고하니 이 문제는 양 끝에서 시작하는 투 포인터가 아니라, 맨 처음부터 같이 시작하는 투 포인터 문제였다.

 

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

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        int[] arr = new int[N + 1];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0, end = 0, total = 0;
        int min = Integer.MAX_VALUE;
        while (start <= end && end <= N) {
            if (total < S) {
                total += arr[end];
                end++;
            } else {
                min = Math.min(min, end - start);
                total -= arr[start];
                start++;
            }
        }

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

 

다른 사람의 풀이를 참고하고도 채점이 70%까지 진행되던 중 실패했는데, 이는 while 반복문을 끊는 조건을 잘못 설정한 문제였다.

 

내가 초기에 세운 while 반복문 조건은 `start < N && end < N` 이었는데, 이는 arr 중간에 부분 합 S를 가뿐히 넘는 값이 존재한다면 start가 end를 넘어서는 순간이 찾아오면서 result 값이 음수가 되면서 반드시 실패하게 된다.

 

그에 따라 한번 더 조정한 조건은 `start <= end && end < N` 이었는데, 문제는 이마저도 실패했다. 풀이를 좀 더 찾아보니 위와 같은 조건은 end가 N에 도달하는 경우 arr의 맨 마지막(N-1 번째) 요소를 탐색하지 못한다는 데 있다.

 

  ※ 문제가 되는 테스트케이스 예시.

  10 1101
  5 1 3 5 10 7 4 9 100 1000

 

이를 고려하기 위해 기존 arr의 크기를 N(그러니까, new int[N+1])으로 맞추고, 조건문을 `.. && end <= N` 으로 수정해줘야만 완전한 정답 판정을 받을 수 있었다.

 

참고 출처

 - https://loosie.tistory.com/630

 - https://moonsbeen.tistory.com/223

---

느낀 점

 

어렵다...