백준 27971 (C++) 강아지는 많을수록 좋다

최초 업로드: 2025-09-24 01:39:21

최근 수정 시간: 2025-09-24 01:39:21

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] 강아지는 많을수록 좋다

[문제 링크](https://www.acmicpc.net/problem/27971)

## 문제 설명

마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 $N$마리를 집에서 키우기로 결심했다!

호무라는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 가장 처음에는 호무라의 집에 강아지가 존재하지 않는다.

그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다. 만약 호무라의 방에 생성된 강아지의 수가 $M$개의 닫힌구간들 ${[L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M]}$ 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 강아지가 사라지게 된다!

이를 명심하면서, 호무라는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 호무라의 집에 정확히 $N$마리의 강아지가 있도록 만들고 싶다. 계산을 어려워하는 호무라를 위해 최소의 행동 횟수를 계산해주자!

## 입력

첫 번째 줄에 키우기를 원하는 강아지의 수 $N (2\leq N\leq 100\,000)$, 제약 사항에 해당하는 닫힌구간의 개수 $M (1\leq M\leq 100)$, 그리고 $A$와 $B (1\leq A,B\leq N)$가 띄어쓰기로 구분되어 주어진다. 그 다음 $M$줄에 걸쳐서, 각 줄에 제약 사항에 해당하는 닫힌구간의 양 끝점이 주어진다. $1\leq i\leq M$에 대하여 $L_i$와 $R_i$는 $1$ 이상 $N-1$ 이하의 정수이며, $L_i\leq R_i$이다.

## 출력

첫 번째 줄에 정확히 $N$마리의 강아지를 호무라의 집에 들일 수 있는 최소의 행동 횟수를 출력한다. 만약 불가능하다면 $-1$을 출력한다.

## 풀이
각 위치에서 방문 가능한지 확인하고, dp[i], dp[i-a]+1, dp[i-b]+1 중 최소를 구했습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100'001;
const int INF = 0x3f3f3f3f;

int minCnt[MAX], l[100], r[100];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m, a, b; cin >> n >> m >> a >> b;
 for(int i=0;i<m;i++) cin >> l[i] >> r[i];

fill(minCnt+1, minCnt+MAX, INF);
 for(int i=1;i<=n;i++) {
 bool chk=false;
 for(int j=0;j<m;j++) {
 if(l[j]<=i && i<=r[j]) {
 chk=true;
 break;
 }
 }
 if(chk) continue;

if(i-a>=0 && minCnt[i-a]>=0) minCnt[i] = min(minCnt[i], minCnt[i-a]+1);
 if(i-b>=0 && minCnt[i-b]>=0) minCnt[i] = min(minCnt[i], minCnt[i-b]+1);
 }
 cout << (minCnt[n]==INF ? -1 : minCnt[n]);
}
```