반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. Two Pointer

2. 사실 1번은 필요없습니다.


이 코드는 left와 right 두개의 배열의 위치를 가리키는 변수로 해결 할 수 있다.


하지만 right를 이용하지 않고도 해결 할 수 있는 방법이 있다.


http://kks227.blog.me/220795165570 이 블로그에서 1번을 이용한 방법을 아주 자세히 적어두어 1번에 대한 설명은 생략한다.


2번에 대한 설명은 아래 소스 코드와 같다.


scanf를 for문 안에 넣어둠으로써 sum을 계속 더해나가고, sum이 만약 ans보다 커지면


left ptr이 가리키는 배열 값을 빼주며 left ptr을 한칸 오른쪽으로 계속 옮겨주는 방식을 취한다면


결국 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
34
35
36
37
#include <cstdio>
#include <vector>
 
using namespace std;
 
int sum, cnt, ptr;
 
int main()
{
    int n, ans;
    vector<int> vc;
 
    scanf("%d %d"&n, &ans);
 
    for (int i = 0; i < n; i++)
    {
        int get;
        
        scanf("%d"&get);
        
        vc.push_back(get);
 
        sum += vc[i];
 
        while (sum > ans)
            sum -= vc[ptr++];
 
        cnt += (sum == ans);
    }
 
    printf("%d\n", cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형