[백준(BOJ)] 2003번 : 수들의 합 2 - C++[CPP]

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

2003번: 수들의 합 2

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 두 포인터

 

---

 

⊙ 문제 접근 과정

 

첫번째 풀이 [ 시간 복잡도 : O(N^2) ]

이중 for문을 통해 문제를 풀었다. 시간 복잡도 O(N^2)이지만 수의 범위(1 <=N <=10,000)가 낮아서 제한 조건에 걸리지 않았다.

 

1. 변수 하나에 일정한 값이 될 때까지 계속 더한다.
2. 만약 m의 값과 일치하면 count up, 변수 초기화
3. 반복

 

두번째 풀이 [ 시간 복잡도 : O(N) ]

투 포인터 알고리즘으로 반복문 하나만을 사용해 문제를 풀었다. 반복문이 하나여서 시간 복잡도는 O(N)이다.

 

1. index를 두개 만들어준다(start, end)
2. start, end 값을 조건에 따라 하나씩 올려주면서 m 값과 비교한다.
3. m값보다 작으면 end 값 상승 후 a[end] 더하기
4. m값과 같으면 count up
5. m값보다 크면 a[start] 값 빼고 start 값 상승

---

 

⊙ 문제 풀이

 

첫번째 풀이 [ 시간 복잡도 : O(N^2) ]

#include <iostream>

using namespace std;

int n,m;
int count=0;
int result;

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

    int a[n+1];

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

    for(int i=0;i<n;i++) {
        for(int j=i;j<n;j++) {
            result += a[j];

            if(result==m) {
                count++;
                result==0;
                break;
            }
        }
        if(result!=0) result=0;
    }   

    cout<< count;
}

 

두번째 풀이 [ 시간 복잡도 : O(N) ]

#include <iostream>

using namespace std;

int n,m;
int count = 0;

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];

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

            if(start>end) {
                end = start;
                result = a[start];
            }
        }
    }

    cout << count;
}

---

⊙ 결과

 

첫번째 결과 [ 시간 복잡도 : O(N^2) ]

 

두번째 결과 [ 시간 복잡도 : O(N) ]

 

---

⊙ 마무리

 

 

NONE

 

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