[백준(BOJ)] 1806번 : 부분합 - C++[CPP]

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

1806번: 부분합

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 두 포인터

 

---

 

⊙ 문제 접근 과정

 

투 포인터 알고리즘으로 풀었다.

 

start, end는 배열 a의 index를 나타낸다. len의 초기값은 N의 최대값인 100,000보다 더 큰 100,001로 설정하고 min과 계속 비교해주어 갱신해주었다. 만약 그러한 합이 불가능하면 len의 값은 100,001이므로 마지막에 len의 값이 100,001 그대로면 0으로 변경해주고 출력해주었다.

 

1. n, m 값 입력
2. n길이의 배열 a 입력
3. end index를 늘려가면서 더해주고 m값과 비교
4. m값보다 작으면 계속 반복
5. 반복하다가 m값과 같아지면 len 값과 현재 길이를 비교해서 더 작은 값을 len에 갱신
6. 그리고 start index 증가 후 값 빼기
7. 반복

 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <algorithm>

using namespace std;

int n,m;

int main() {
    cin >> n >> m;

    int a[n+1];

    for(int i=0;i<n;i++) {
        cin >> a[i];
    }

    int start=0,end=0;
    int result = a[0];
    int len=100001;

    while(start<=end && end<n) {
        if(result<m) {
            result+=a[++end];
        } else if(result>=m) {
            len=min(end-start+1,len);
            result -=a[start++];
            if(start>end) {
                end = start;
                result = a[start];
            }
        }
    }

    if(len==100001) {
        len=0;
        cout << len;
    } else cout << len;
}

---

⊙ 결과

 

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!