(백준) 13422 - 도둑 [java]

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

🐢 설명

N개의 집을 연속적으로 M번 골라서 K원 미만의 금액이 되는 조합을 구하면 되는 문제이다.

 

집들이 원형 구조라서 N-1번집은 0번집과 연결되어있다는 점과 N과 M이 동일할 경우 N개의 집에서 연속적으로 M개를 고르는 조합은 모두 동일하다는 점을 주의하면 된다.

 

예를들어 집이 3개가 있고 연속적으로 3개의 집을 털어야하는 경우를 생각해보자.

• A B C의 집을 돈다면
• 1) A -> B -> C
• 2) B -> C -> A
• 3) C -> A -> B, 총 3가지 경우가 존재한다.

하지만 결국 턴 집은 A, B, C로 동일한 조합이므로 이를 처리해 줘야한다.

 

그래서 N == M 인 경우만 예외로 빼주고 나머지는 투포인터로 고른 집이 M개이면서 턴 돈이 K 미만인지 확인해주면 된다.

 

🐢코드

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

public class 도둑_13422 {
    static int T, N, M, MAX;
    static int[] houses;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();

        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            String[] input = br.readLine().split(" ");
            N = Integer.parseInt(input[0]);
            M = Integer.parseInt(input[1]);
            MAX = Integer.parseInt(input[2]);

            houses = Arrays.stream(br.readLine().split(" "))
                    	.mapToInt(Integer::parseInt)
                    	.toArray();

            answer.append(solution()).append("\n");
        }
        System.out.print(answer);
    }

    private static int solution() {
        int left = 0;
        int right = 0;
        int total = 0;
        int cnt = 0;

        while (left < N) {

            total += houses[right % N];

            // find
            if (right - left + 1 == M && total < MAX) {
                cnt++;
                if (N == M) cnt = 1;
            }

            // over
            while ((left < N && total >= MAX) || right - left + 1 == M)
                total -= houses[left++];

            ++right;
        }

        return cnt;
    }
}

 

🐢 마무리

조합의 개수를 구하는 것을 명심하자.