[코딩테스트] [BOJ2003] 수들의 합 2

문제

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

---

풀이

작동 코드

1. 반복문 두개 돌려서 값 다 더하는 방식으로, O(n^2)의 시간복잡도가 나옴

2. 문제 조건이 넉넉해서 넘어갔는데, 개선이 필요하다 느껴 지피티 도움받음

개선 코드

1. left : 합에 포함되는 가장 왼쪽 인덱스 / right : 합에 포함되는 가장 오른쪽 인덱스를 활용한다.

2. 만약 현재 총 합이 m 이상이라면, m과 같았을 때 count를 증가시킨다.
   2-1. 현재 총 합에서 left에 해당하는 요소 값을 빼주고, left를 증가시킨다.

3. 만약 right가 n과 같다면, 배열의 끝이라는 뜻이므로 while문을 빠져나온다.

4. 모든 경우의 수에 포함이 안 된다면, 현재 총 합이 m보다 작고 right 값이 배열의 끝도 아니라는 뜻이다. 따라서 총 합에 현재 right에 해당하는 요소 값을 더해주고, right를 증가시킨다.

---

작동 코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;

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

    int total = 0;
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        total += temp[i];

        if (total == m)
        {
            count++;
            total = 0;
            continue;
        }

        for (int j = i + 1; j < n; j++)
        {
            total += temp[j];

            if (total == m)
            {
                count++;
                break;
            }
            else if (total > m)
            {
                break;
            }
        }
        
        total = 0;
    }

    cout << count;

    return 0;
}

---

개선 코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;

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

    int total = 0;
    int count = 0;
   
    int left = 0;
    int right = 0;

    while (true)
    {
        if (total >= m)
        {
            if (total == m)
            {
                count++;
            }

            total -= temp[left];
            left++;
        }
        else if (right == n)
        {
            break;
        }
        else
        {
            total += temp[right];
            right++;
        }
    }

    cout << count;

    return 0;
}