백준(BOJ) 13422 도둑 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/13422

13422번: 도둑

풀이에 이용된 알고리즘: 투포인터, 구현

 

투포인터라고는 하였지만, 구현에 가깝다고 생각된다.

 

1. 어떤 입력데이터의 시작과 끝을 연결해주기 위해서, 원형 리스트 등의 복잡한(?) 자료구조 도입을 고민할텐데, 단순히 입력 데이터 시퀀스를 두 번 연속하여 1차원 배열에 저장해주면 된다.

 

ex1) 입력데이터가 1 3 5라면, 단순히 1 3 5 1 3 5로 배열에 저장해두도록 한다. (m이 n 이하이기 때문에 두번만 연속해도 괜찮고, 데이터에 접근할 때 여러번의 싸이클이 발생하다면 다른 방법이 필요할 것이다.)

 

ex2) 입력데이터가 1 7 5 2 9이고 m = 3, k =  17인 경우 풀이는 다음과 같다.

 

ex1의 아이디어를 적용하여 원소를 1 7 5 9 2 1 7 5 9 2로 두고, m이 3이므로 앞에서부터 3개씩 원소의 합을 구한다. 이 때 합을 구하기 시작하는 각 서브시퀀스의 시작 원소를 1번째부터 n번째까지의 원소로 둔다.

 

1 + 7 + 5 = 13

7 + 5 + 9 = 21

5 + 9 + 2 = 16

9 + 2 + 1 = 12

2 + 1 + 7 = 10

 

이 중 k(17) 이하인 경우는 총 16, 12, 10으로 3가지이므로 답은 3이 된다.

 

 

2. n과 m인 같은 경우에는 ex2)처럼 서브 시퀀스들의 합을 구해도, 모두 같은 경우가 돼버리므로 총 원소의 합이 k 미만인지 단 한 번만 확인할 수 있도록 한다.

 

예를 들어, n=m=3이어서 입력이 1 5 2라고 하면 1 5 2 1 5 2에 대해, 1 + 5 +2, 5 + 2 + 1, 2 + 1 + 5가 되는데 순서만 다를 뿐 모두 같은 원소들로 구성된 서브 시퀀스의 합을 구한 것이나 마찬가지다.(애초에 n=m이면 시퀀스와 서브시퀀스가 완전히 동일한 한 가지의 경우뿐 존재하는 것임을 상기하면 직관적으로 이해가 될 것이다.)

 

3. 서브 시퀀스의 합을 구할 때, for문을 이용하여 정직하게 구하는 것 보다는, 바로 직전 단계의 서브시퀀스의 합 sum에서, 가장 앞 원소를 제거해주고 새로운 서브 시퀀스 구성을 위해 추가된 원소의 값을 합쳐주는 방식으로 연산 횟수를 줄일 수 있다.(이렇게 하지 않으면 시관초과 발생!)

 

/* BOJ 13422 도둑 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int t, T, n, m, k;
int arr[200001];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> T;
    for (t = 1; t <= T; t++)
    {
        cin >> n >> m >> k;
 
        for (int i = 1; i <= n; i++)
        {
            int a;
            cin >> a;
            // 배열의 시작과 끝이 연결된 원소이므로
            // 배열을 두배로 확장하여 시퀀스를 두번 반복
            arr[i] = a, arr[i + n] = a;
        }
 
        if (n == m)
        {
            // n == m이면 완전히 동일한 경우가 반복되므로 한번만 확인
            int sum = 0;
            for (int i = 1; i <= n; i++)
                sum += arr[i];
 
            if (sum < k)
            {
                cout << 1 << endl;
                continue;
            }
        }
 
        int cnt = 0, sum = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i == 1)
            {
                for (int j = 0; j < m; j++)
                    sum += arr[i + j];
            }
 
            else
                sum = sum - arr[i - 1] + arr[i - 1 + m];
 
            if (sum < k)
                cnt++;
        }
 
        cout << cnt << endl;
    }
 
    return 0;
}