도둑
문제 해석
연속된 M개 집의 돈을 훔치되, 돈의 양 K보다 적은 돈을 훔칠 수 있는 경우의 수를 구하는 문제입니다.
각각의 집은 순서대로 서로 이웃해 있으며, 첫 번째 집과 마지막 집 또한 이웃해 있습니다.
설계(10)
sliding window기법을 이용하는 문제입니다.
처음에 M개의 집에 있는 돈의양의 합을 구합니다.
만약 돈의 양이 K보다 적은 경우, 카운트합니다.
1~N 집부터 시작하는 연속된 M개의 돈의 양을 각각 구하고, K보다 적은경우 카운트합니다.
집에 원모양으로 되어있으므로, 모듈러연산을 이용합니다.
주의할 점은 똑같은 집 조합을 여러번 훔치는 경우를 판단하기 위해서, (i+M-1)%N== i-1이면 break하도록 합니다.
구현(10)
코드
#include <iostream>
using namespace std;
#define MAXN 100000
int arr[MAXN];
int N,M,K,ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--){
cin >> N >> M >> K;
for (int i = 0 ;i <N; i++){
cin >> arr[i];
}
ans = 0;
int money= 0;
for (int i = 0 ;i < M; i++){
money += arr[i];
}
if (money<K) ans++;
for (int i = 1; i < N; i++){
if ((i+M-1)%N == i-1) break;
money -= arr[i-1];
money += arr[(i+M-1)%N];
if (money < K) ans++;
}
cout << ans <<"\n";
}
return 0;
}
디버깅
질문게시판의 반례를 보고 잘못된 점을 파악했습니다.
2 3 5
1 1 1
이 반례로 1-2-3을 훔치고 2-3-1,3-1-2를 훔치는 현상을 발견하였습니다.
이를 방지하기 위해서, 훔치는 집 시작점+M개가 모든 집을 훔치는 경우 다음 집은 탐색하지 않도록 변경하였습니다.
제출결과
88 ms
마무리
sliding window를 활용한 문제였습니다.
문제가 아주 직관적으로 설명이 잘 되어있어서 풀이가 쉬웠던 것 같습니다.