BOJ 1806번: 부분합

1. 문제 상황

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제

// 입력
10 15
5 1 3 5 10 7 4 9 2 8
//출력
2

// 입력
10 14
5 1 3 5 10 7 4 9 2 8
//출력
2

// 입력
10 30
15 1 1 1 1 1 1 1 1 15
//출력
10

// 입력
6 10
1 1 1 1 1 13
//출력
1

// 입력
10 10
1 1 1 1 1 1 1 1 1 10
//출력
1

// 입력
10 30
1 1 1 1 1 1 15 1 1 15
// 출력
4

2. 내 답안

코드 보기

#include <iostream>

using namespace std;

int main() {
    int N, S, tmp;
    int left, right;
    int inps[100001], sums[100001];

    scanf("%d %d", &N, &S);
    inps[0] = 0;
    sums[0] = 0;
    for (int i=1;i<=N;i++) {
        scanf("%d", &tmp);
        if(tmp > S) {
            printf("1\n");
            return 0;
        }
        inps[i] = tmp;
        sums[i] = sums[i-1] + tmp;
    }
    if (sums[N] < S){
        printf("0\n");
        return 0;
    }

    // two pointers
    left = 0;
    right = 1;
    int ans = N+100;
    while (left<=N && right<=N) {
        // printf("%d~%d: %d\n", left, right, sums[right]-sums[left]);
        if (sums[right] - sums[left] < S) { // 현재 부분합이 S보다 작으면 right++
            right++;
        } else { // 현재 부분합이 S보다 크면 고려대상
            if (right-left<ans) ans = right - left; // 현재 포인터들이 최소값 후보면 일단 최솟값을 바꾸고
            if (right-left > 1) { // right가 left 한 칸 옆에 있으면 둘 다 옮기고 아니면 left만 옮김
                left ++;
            } else {
                left++;
                right++;
            }
            
        }
    }
    printf("%d\n", ans);
    return 0;
}

3. 첨언

그냥 별 다를 것 없는 두 포인터 유형의 문제였다.
질문게시판을 돌아다니며 보이는 모든 반례를 넣어봤는데 왜 안되는지 모르겠어서 문제 생길만 한 부분을 모조리 조금씩 건들다 보니 틀린 횟수가 너무 많아졌따..
알고보니 30번 줄에 초기 최댓값을 N으로 뒀었다….
앞으로 반례 좀 넣어보고 포기하지 말고 생각 좀 해야하겠다
반성하자..

1. 문제 상황

2. 내 답안

3. 첨언

Enjoy Reading This Article?