백준, BOJ, 2003번 C++ [CPP]

 

바로 생각한 대로 실행하면 되는 문제다.

 

 

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

 

---

 

우선 N~M번째 까지의 합은

1~M - 1~N-1 인것을 나는 이용했다.

 

하지만 이제부터는 잘한 사람들에게서도 나와 무엇이 다른지 공부하기로 했다 우선 

나의 풀이를 보고 다른 잘한 사람들의 풀이를 비교해보자

 

#맞은 풀이

#include <iostream>

using namespace std;

int N,M;

int arr[10001];
int dp[10001]; // dp[i] -> 1~i번째까지의 합

// N~M 까지의 합은 1~M번째 까지의 합 - 1~N-1 번째까지의 합.

int main(){
    cin >> N >> M;
    int cnt = 0;
    
    for(int i=1; i<=N; i++){
        cin >> arr[i];
        dp[i] = dp[i-1] + arr[i];
    }
    for(int j = N; j>=1; j--){
        for(int i = 1; i<=j; i++){
            if(dp[j]-dp[i-1] == M){
                cnt++;
            }
        }
    }
    
    cout << cnt;
}

 

#다른 사람 풀이

 

#include<cstdio>
int i;
int sum;
int dap;
int left;
int main()
{
    int n, m, a[10005];
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++)
	{
		scanf("%d", a + i); // 0번 인덱스부터 채워넣으면서 sum 계산.
		sum += a[i];	//순서대로 더하면서 0~N까지 계산
		while (sum > m)  // 만약 M보다 작아지거나 같아질 때까지 앞의 원소를 삭제.
		sum -= a[left++];

		dap += sum == m; // M과 같아졌다면 해당 값 카운트
	}
	printf("%d\n", dap);
}

 

나와 다른 것은..

나는 전부 조사한다면

이 사람은 입력받으면서 조사하기에 시간이 절약된다는 것

 

처음부터 이 풀이를 생각하기는 어려울 것 같다...

아무튼 저 사람은 정말 이해를 잘하고 이용을 했다.

 

즉, 나는 j를 1부터 했지만 저 사람은 M이 넘는 순간에만 조사하는 것이다.

이것이 더 효율적이긴 하네