16568번 : 엔비스카의 영혼

엔비스카의 영혼

시간 제한               메모리 제한                       제출                           정답                  맞힌 사람           정답 비율

 

2 초

512 MB

1045

365

280

36.269%

 

문제

한길이는 수습 마법사이며, 마법사의 영혼을 받기 위해 줄을 서있다. 한길이는 강력한 힘을 얻기 위해 인성을 버렸다. 그리고 최고로 강력한 엔비스카의 영혼을 받기 위해서 새치기를 하기로 결심했다.

한길이의 앞에 N명의 사람들이 줄 서있다. 1초가 지날 때마다 줄의 맨 앞 사람은 영혼을 받고 집에 간다. 그리고 1초마다 한길이는 다음과 같은 행동을 할 수 있다.

기다리기
a명 앞으로 가기 (앞에 최소 a명 있을 때)
b명 앞으로 가기 (앞에 최소 b명 있을 때)
단, 한길이는 새치기에는 도가 텄기때문에, 모든 행동을 0초만에 할 수 있다.

예를 들어 N = 5, a = 1, b = 2라고 하자. 5초동안 기다리기만 하면 줄의 맨 앞 사람이 나가기 때문에 줄의 맨 앞에 서있기까지 5초가 걸린다. 하지만 맨 앞 한 명이 집에 가고 한길이가 2명 앞으로 새치기, 그 다음 한 명이 집에 가고 1명 앞으로 새치기하면 2초만에 줄의 맨 앞에 서게 된다. 유의할 점은 1초에 맨 앞 한 명이 가고 2명 앞으로 새치기하고 맨 앞 한 명이 가면 1명이 남는다. 이 때 2명 앞으로 새치기는 불가능하다.

한길이가 줄의 맨 앞에 서있으려면 최소 몇 초가 걸리는가?

입력
첫째 줄에 N, a, b가 주어진다. (0 ≤ N ≤ 1,000,000, 0 ≤ a, b ≤ N)

출력
한길이가 맨 앞에 서는데 걸리는 최소 시간을 출력한다.



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

16568번: 엔비스카의 영혼

 

정답

//16568 - 엔비스카의 영혼 (DP)
// OOOOOOO
//홀수: N-2-1
//짝수 : N
#include <bits/stdc++.h>
using namespace std;
int N, a, b;
int dp[1000004];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> N >> a >> b;
    //2. dp 수행
    for(int i=1;i<=N;i++){
        dp[i]=dp[i-1]+1; //1초씩 지남
        //a와 b 중 더 빠른 것 선택
        if(i-a-1>=0){ //1명이 집에 가고 a명이상 앞에 남아있을때
            dp[i]=min(dp[i],dp[i-a-1]+1); //1초 지난 것 적용
        }
        if(i-b-1>=0){ //1명이 집에 가고 b명이상 앞에 남아있을때
            dp[i]=min(dp[i], dp[i-b-1]+1);
        }
    }
    //3. 정답 출력
    cout<<dp[N];
}