[백준]13422: 도둑 - JAVA

[백준]13422: 도둑

13422번: 도둑

풀이

🪑 문제가 장황하게 적혀있지만 한 줄로 정의할 수 있는 문제였다. 간단한 투포인터 문제이다.

 

📝 문제를 정리해 보자

• N개의 집들 중에서 M개의 연속된 집을 선택하여 K이하의 돈을 훔칠 수 있는 경우의 수를 구하는 문제이다.

문제 구현에 대한 아이디어는 굉장히 쉽지만, 엣지 케이스가 있으니 유의해야 한다. 문제가 쉽다고 무턱대고 구현했다가 엣지 케이스에서 걸려버렸다 ㅠ

 

 

🔧 이제 풀어보자!

1. 입력 받은 정보를 저장한다. 
2. 집들은 항상 연속된 M개를 선택해야 하므로 이 크기를 유지한 채로 투포인터를 진행한다.

 

🔹 입력 받은 정보를 저장한다. 

- 이때 각각의 집에서 보관중인 돈의 양의 총합도 구해주었다.

 

🔹 집들은 항상 연속된 M개를 선택해야 하므로 이 크기를 유지한 채로 투포인터를 진행한다.

- start와 end가 항상 m만큼 차이나도록 하였다. 초기 start와 end만큼의 sum을 구해주는 로직을 추가해 주었다.

- start가 n보다 작은 동안만 탐색하며, 현재 돈의 합이 k보다 작은지 확인하여 count를 ++한다.

- 그 다음으로 m의 크기를 유지하여 다음 집을 확인하며 이때 기존의 sum에서 start에 해당하는 집의 값은 빼주고, 추가로 포함될 end에 해당하는 집의 값을 더해준다. end는 n의 크기를 넘을 수 있으므로 나머지 연산을 해주었다.

 

 

🙋‍♀️ 이 문제에서 발생할 수 있는 엣지 케이스는 다음과 같다!

n과 m이 같을때 n개의 집들이 가진 돈의 총 합이 k 미만이다.

n과 m이 같을때 n개의 집들이 가진 돈의 총 합이 k 이상이다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int t = Integer.parseInt(bf.readLine());
        for(int i = 0; i < t; i++) {
            String str = bf.readLine();
            StringTokenizer st = new StringTokenizer(str);
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
 
            int[] home = new int[n];
            str = bf.readLine();
            st = new StringTokenizer(str);
            int total = 0;
            for(int j = 0; j < n; j++) {
                home[j] = Integer.parseInt(st.nextToken());
                total += home[j];
            }
            //입력 끝
 
            if(n == m) {
                if(total < k) System.out.println("1");
                else System.out.println("0");
            } else {
                int count = 0;
 
                int start = 0;
                int end = m - 1;
                int sum = 0;
                for(int j = 0; j <= end; j++) {
                    sum += home[j];
                }
 
                while(start < n) {
                    if(sum < k) count++;
                    sum -= home[start++];
                    sum += home[(++end) % n];
                }
                System.out.println(count);
            }
        }
    }
}