[BOJ] 백준 13422 : 도둑 (java)

🧪 13422 도둑

---

난이도 : 🌟 골드 4
유형 : 투포인터

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

 

📝 문제

---

 

다음 그림과 같이 N개의 집이 순서대로 이웃하여 세워진 마을이 있다.

위 그림은 N = 8인 경우 마을의 모습이다. 위 그림과 같이 각각의 집은 순서대로 서로 이웃해 있으며, 첫 번째 집과 마지막 집 또한 이웃해 있다. 예를들면 3이 적힌 집은 9, 4가 적힌 집과 이웃해 있으며, 5가 적힌 집은 6, 7이 적힌 집과 이웃해 있다. 이 마을 사람들은 각자 자신의 집에 돈을 보관한다. 위 그림에서 각 집에 적혀 있는 숫자는 집마다 보관 중인 돈의 금액을 나타낸다. 어느 날 이 마을에 도둑이 들었다. 도둑은 이 마을에서 어떻게 도둑질을 할까 잠시 고민하다가, 빠르게 돈을 훔치고 달아나기 위해 M개의 연속된 집에서 돈을 훔치되, 돈을 훔칠 때는 각 집에 보관중인 돈을 전부 훔치기로 했다. 예를 들어 M = 3일 때, 위 그림에서 순서대로 3, 4, 7의 돈을 보관중인 집에서 총 14의 돈을 훔친 후에는 더 이상 돈을 훔치지 않고 달아나야 한다. 또 다른 예로는 순서대로 5, 6, 4의 돈을 보관중인 집에서 총 15의 돈을 훔친 후에는 달아나야 한다. 그러나 만약 도둑이 이 마을에서 총 K원 이상의 돈을 훔친다면 자동 방범장치가 작동하여 도둑은 바로 붙잡히게 된다. 예를 들어 M = 3, K = 15인 경우 위 그림에서 순서대로 3, 4, 7의 돈을 보관중인 집에서 도둑질을 한다면 총 도둑질한 돈이 14가 되어 붙잡히지 않고 달아날 수 있지만, 순서대로 5, 6, 4의 돈을 보관중인 집에서 돈을 훔친다면 총 도둑질한 돈은 15가 되고, 방범장치가 작동하여 도둑은 붙잡히게 된다.

마을을 이루고 있는 집의 개수 N, 도둑이 돈을 훔쳐야 할 연속된 집의 개수 M, 자동 방범장치가 작동하는 최소 돈의 양 K와 각 집에서 보관 중인 돈이 순서대로 주어질 때, 도둑이 붙잡히지 않고 무사히 마을을 빠져나가기 위해 돈을 훔칠 M개의 연속된 집을 고르는 방법의 수를 출력하는 프로그램을 작성하시오.

 

입력

 

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마을에 있는 집의 개수 N(1 ≤ N ≤ 100,000), 도둑이 돈을 훔칠 연속된 집의 개수 M(1 ≤ M ≤ N), 자동 방범 장치가 작동하는 최소 돈의 양 K(1 ≤ K ≤ 1,000,000,000, K는 정수)가 공백으로 구분되어 주어진다. 테스트 케이스의 둘째 줄에는 N개의 집에서 각각 보관중인 돈의 양이 시계방향 순서대로 공백으로 구분되어 주어진다. 돈의 양은 각 집이 이웃해 있는 순서대로 주어진다. 첫 번째 집과 마지막 집 또한 이웃하기 위해 입력의 첫 번째와 마지막이 서로 연결되어 있다고 가정하며, 각 집에서 보관 중인 돈의 양은 1이상 10,000이하의 정수이다.

 

출력

 

출력은 표준 출력을 사용한다. 입력 받은 데이터에 대해, 도둑이 자동 방범장치에 붙잡히지 않도록 연속된 M개의 집에서 돈을 훔치는 방법의 가짓수를 한 줄에 1개씩 출력한다.

 

🚧  주의할 점

---

1. 1~9번의 집이 있다면 9에서 1번집으로 갈 수 있음을 주의하며 풀이한다.
2. 입력이 [3 3 5] [1 1 1] 이라면 1 > 2 > 3 , 2 > 3 > 1, 3 > 1> 2가 모두 cnt에 누적돼 답이 3이 나오게된다. 이를 방지하기 위해 n == m 일때 break 하도록 한다.

🧐 핵심 로직 

---

1. 입력으로부터 여러 테스트 케이스를 처리하며 주어진 조건을 만족하는 구간의 개수를 계산한다.

 

2. 외부 반복문에서 각 테스트 케이스를 처리한다.

    2 - 1) 첫 줄에서 n(배열 길이), m(구간 길이), k(비교 기준 값)을 읽어온다.

    2 - 2) 두 번째 줄에서 n개의 정수를 읽어 moneys 배열에 저장한다.

 

3. 구간 합을 이용해 조건을 만족하는 구간의 개수를 계산한다.

    3 - 1) 초기 sum은 0으로 설정하고, 구간 시작 시점에서 구간 끝까지 누적합을 계산한다.

    3 - 2) 배열의 요소를 순회하며, 현재 요소를 합산하고 sum 값이 k보다 작으면 구간의 개수를 증가시킨다.

    3 - 3) 구간 길이 m을 초과한 경우, 가장 오래된 요소를 sum에서 빼 구간 합을 유지한다.

 

4. 만약 배열 길이 n이 구간 길이 m과 같을 경우 순환 계산을 피하기 위해 내부 루프를 일찍 종료한다.

 

5. 각 테스트 케이스의 결과를 StringBuilder에 저장하고, 모든 테스트 케이스를 처리한 후 출력한다.

 

💻 최종 코드 (528 ms)

---

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

public class Main {

    static int testCase, n, m, k;
    static int[] moneys;
    static StringBuilder res;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        testCase = Integer.parseInt(br.readLine());
        res = new StringBuilder();
        for (int t = 1; t <= testCase; t++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st1.nextToken());
            m = Integer.parseInt(st1.nextToken());
            k = Integer.parseInt(st1.nextToken());

            moneys = new int[n];
            int sum = 0;
            int cnt = 0;
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for (int i = 0; i < n + (m - 1); i++) {
                if (i < n) {
                    moneys[i] = Integer.parseInt(st2.nextToken());
                    sum += moneys[i];
                } else {
                    sum += moneys[i - n];
                }

                if (i >= m - 1) {
                    if (sum < k) {
                        cnt++;
                    }
                    sum -= moneys[i - (m - 1)];
                }

                if (n == m && i == n - 1) break;
            }

            res.append(cnt).append("\n");
        }

        System.out.println(res);

        br.close();
    }
}