백준 알고리즘 2003 수들의 합2

략간스트,, 처음에 문제 파악(?)하는데 쬐에끔 걸렸다ㅋㅋㅋ

말 그대로 숫자를 N개대로 입력 받고, 합쳐서 M이 나오는 경우의 수를 구하는 것인데, 연속된 숫자들을 합했을 때 M이 나오는 경우의 수이다. 근데 지금 보니까 문제를 잘못 풀은 것 같다. 전부 예전에 풀었던 문제들을 다시 공부하는 차원에서 정리하는 중인데 '투 포인터'라는 개념을 사용해서 풀어야 하는 것 같다. 일단은 내가 풀었던 코드 정리 한 번하고 다음에 다시 투 포인터라는 개념을 가지고 풀어봐야겠다.

나는 그냥 배열에 때려박았숨다. >.<

문제에서는 입력받을 숫자갯수는 N, 연속된 수의 합은 M으로 지정했는데 코드에서는 num과 sum으로 선언했다.(N = num, M = sum)

그냥 차례대로 더하면서(이 숫자는 sum_에 저장) sum과 같아지면 count++해 주고 sum을 넘기면 한칸 옆으로 넘어가서(k++) 다시 숫자들을 연속적으로 합해주었다. 참 쉽죠잉...?ㅎ... 

그르니께 그림으로 간단하게 설명하자면 다음과같이 k가 num-1번째까지 반복하는 것이닷,,,

코드에 설명을 주석으로 추가로 달아 놓았당

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
int main(void) {
    //num은 입력받을 숫자 갯수, sum은 연속된 숫자들의 합, arr은 입력받을 숫자들을 저장할 배열
    int num, sum, *arr; 
    scanf("%d %d", &num, &sum);
 
    //배열의 크기를 할당해 주고 배열에 숫자들을 저장해 줌
    arr = (int *)malloc(num * sizeof(int));
    for (int i = 0; i < num; i++)
        scanf("%d", &arr[i]);
    
    //k는 시작점, sum_은 연속된 숫자들의 합, count는 경우의 수
    int k = 0, sum_, count = 0;
 
    //k는 배열의 마지막까지 옮겨가야함
    while (k < num) {
 
        //sum_을 0으로 초기화 시킴
        sum_ = 0;
 
        //인덱스k번째부터 배열의 숫자들을 더해
        for (int i = k; i < num; i++) {
            sum_ += arr[i];
 
            //sum과 같아지면 count++해 주고 for문을 빠져나감
            if (sum_ == sum) {
                count++;
                break;
            }
            
            //sum보다 커지면 더 이상 더해 줄 필요가 없으므로 for문을 빠져나감
            else if (sum_ > sum)
                break;
        }
        
        //시작점을 한 칸 옆으로!
        k++;
    }
    printf("%d", count);
    free(arr);
    return 0;
}
 

흑... 알고리즘 공부 좀 열심히해야겠다...