[백준 13422번] 도둑 - java

문제 설명

1. 맨 윗줄은 테스트 케이스 갯수

2. 2줄씩 받고 -> 처음은 [집갯수, 훔칠 집 수, 훔칠 금액 최대값+1] / 두번째는 [집들의 가진 돈] 이 주어진다.

3. 도둑이 훔치려고 할 때에 인접한 집을 찾아가면서 훔치고 일정 금액 이상 훔치거나 일정 집 수 이상 훔치면 잡혀감

4. 그 안에서 훔칠 경우의 수를 구하면 된다.

 

풀이 과정

 1. 간단한 슬라이딩 윈도우 문제이다.

 2. 집을 하나씩 찾으면서 보면 된다.

 3. 그리고 보면 그냥 배열이랑 좀 다른거는 처음 맨 뒤쪽 집들은 최초 털어간 집에 대한 확인도 된다는거

 4. 내가 풀어낸 방식은 그래서 [123][234][345][451][512] 이렇게이다.

 5. 근데 여기서 중요한건 M == N 이면, 4번 방식에서 [123][231][312] 가 된다. 그래서 미리 확인해야 한다.

 

코드

ㄱㅂㄷㄱㅂㄷㄱ

import java.util.*;

public class Main
{
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 테케 수
        int T = Integer.parseInt(sc.nextLine());
        
        while(T-->0) {
            int ans = 0;
            String input = sc.nextLine();
            
            int[] intArray = Arrays.stream(input.split(" "))
                                   .mapToInt(Integer::parseInt)
                                   .toArray();
                                   
            int houseCnt = intArray[0];
            int moneyCnt = intArray[1];
            int moneyMax = intArray[2] - 1;
        
            input = sc.nextLine();
            
            int[] houseArr = Arrays.stream(input.split(" "))
                                   .mapToInt(Integer::parseInt)
                                   .toArray();
                                   
            long money = 0;
            
            // 털 집 수랑 전체 집 수가 같으면
            if (houseCnt == moneyCnt) {
            	// 전체 집 금액 구해서
                for (int i = 0; i < houseCnt; i++) {
                    money += houseArr[i];
                }
                // 내가 털어도 된다 싶으면 그게 다임
                if (money <= moneyMax) {
                  System.out.println(1);
                  continue; // 그러면 뒤에는 안하면 된다.
                }
            }
            
            // 처음 집부터 시작해서 맨 뒤 집쪽에서 다시 처음으로 돌아오기 위해 설정
            for(int i=0; i<houseCnt + moneyCnt - 1; i++) {
            	// 집 털 숫자 되면 이전집 제거
                if(i >= moneyCnt) {
                    money -= houseArr[i - moneyCnt];
                }
                
                // 다음집 털 금액 확인 -> %해서 배열 넘어가면 처음으로 돌아간다.
                money += houseArr[i % houseCnt];
                
                // 그래서 요만큼 털때 돈 이정도면 된다 하면 털어도 됨.
                if (i >= moneyCnt - 1 && money <= moneyMax) {
                    ans++;
                }
            }
            
            System.out.println(ans);
        }
    }
}