Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

차근차근

[백준 2003] 수들의 합 2 본문

대학교/Algorithm

[백준 2003] 수들의 합 2

SWKo 2020. 2. 29. 12:44

0. 제목

  • 백준 2003 수들의 합 2
  • BOJ 2003 수들의 합 2
  • C++ 2003 수들의 합 2

1. 문제

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


2. 풀이

  • startIdx를 이용해 합의 시작점을 저장해준다.
  • sum이 구하고자 하는 합 M과 같아지면 가능한 경우의 수인 cnt를 1증가시켜주고 M을 넘어가면 while문을 빠져나간다.
  • 만약 while문에서 sum이 M보다 작고 startIdx가 배열의 마지막 원소를 지나치면 즉, N+1 이 되면 while문을 빠져나온다.
  • cnt를 출력하면 정답니다.
  • 그런데 이러한 문제는 투포인터를 사용한다고 하면 된다. 위 방법도 그와 비슷한 방법이지만 투포인터의 내용을 살려 또 다른 코드를 첨부하겠다.
  • 투포인터 방식을 사용하면 위 방식보다 시간을 줄일 수 있다. 
  • 투포인터 방식은 low, high 두 포인터를 설정해 놓은 후 sum의 크기에 따라 low와 high가 가리키는 위치를 조정하는 것이다. 
  • high가 N이 되면 while문을 빠져나가고 그 내부에서는 sum이 M보다 커자면 low가 가리키는 값을 빼주고 high가 가리키는 값을 더해준다.
  • low로 빼고 high로 채워준다고 생각하면 될 것 같다.

3. 코드

  • 방법 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int A[10001= {0};
    int N, M;
    int cnt = 0;
    int startIdx = 1;
    int sum = 0;
    
    cin >> N >> M;
    for(int i = 1; i <= N; i++)
        cin >> A[i];
    
    for(int i = 1; i <= N; i++){
        startIdx = i;
        sum = 0;
        while(1){
            if(startIdx == N+1break;
            sum += A[startIdx];
            if(sum == M){
                cnt++;
                break;
            }
            else if(sum > M)
                break;
            startIdx++;
        }
    }
    cout << cnt << '\n';
    return 0;
}
 
 

 

  • 방법 2 (투포인터 방식)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int A[10001= {0};
    int N, M;
    int l = 0, h = 0;//low, high
    int sum = 0, cnt = 0;
    
    cin >> N >> M;
    for(int i = 0; i < N; i++)
        cin >> A[i];
    
    while(1){
        if(sum >= M) sum -= A[l++];
        else if(h == N) break;
        else sum += A[h++];
        
        if(sum == M) cnt++;
    }
    
    cout << cnt << '\n';
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 7576] 토마토  (0) 2020.03.01
[백준 2022] 사다리  (0) 2020.02.29
[백준 1789] 수들의 합  (0) 2020.02.29
[백준 1932] 정수 삼각형  (0) 2020.02.28
[백준 1735] 분수 합  (0) 2020.02.27
Comments