[백준 13422번] 도둑

문제 링크: 13422번 제목

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

 

문제를 읽기만 해도 풀이가 보일 듯한 쉬운 문제로 보입니다. 네, 실제로 쉬운 문제가 맞습니다. 하지만, (슬라이딩 윈도우로 푼다는 가정 아래에) 숨겨진 함정이 하나 있습니다.

바로 n과 m이 같을 때입니다.

 

일단 n = 4, m = 3이면 어떨까요? 처음 2가지 경우만 보더라도, 윈도우를 이동시켰을 때 서로 다른 부분집합이 선택된다는 것을 알 수 있습니다. {1, 2, 3}, {2, 3, 4}, {3, 4, 1}, {4, 1, 2} 이렇게요.

 

하지만 n = m = 4인 경우는 어떨까요? 마찬가지로 처음 2가지 경우만 보겠습니다. 이 때에는 윈도우를 이동시켜도 동일한 부분집합이 선택된다는 것을 알 수 있습니다. 곧 {1, 2, 3, 4}의 1가지 경우로서 답은 1임에도 불구하고, 오답인 4를 도출해내게 됩니다.

 

코너 케이스를 잡기 힘들었던 건, n = 1이나 m = 1과 같은 경계값에서 코너 케이스를 찾는 습관이 들어서 그랬던 것 같습니다. 물론 WA를 보기 전까지 코너 케이스가 있다는 것조차 생각해내지 못했고요.

 

더 꼼꼼한 풀이를 위해 노력해야 하는 것도 있겠지만, 이번 문제와 같은 경우는 코너 케이스가 안 떠오르기 십상이기 때문에, 지금처럼 당해보면서 조심해야 할 유형을 익혀나가는 것도 좋은 전략일 것 같습니다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int m;
    static int k;
    static int[] a;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());
        while (test-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            a = new int[n];
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }
            solve();
        }
        System.out.print(sb);
    }

    static void solve() {
        int cnt = 0;

        int l = 0;
        int r = m - 1;
        int s = s(l, r);
        if (s < k) cnt++;
        if (n != m) {
            while (true) {
                s -= a[l];
                l++;
                r++;
                s += a[r % n];
                if (l >= n) break;
                if (s < k) cnt++;
            }
        }

        sb.append(cnt).append('\n');
    }

    static int s(int l, int r) {
        int ret = 0;
        for (int i = l; i <= r; i++) {
            ret += a[i];
        }
        return ret;
    }
}