[BAEKJOON] 16568번 엔비스카의 영혼 (DP, C++)

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

16568번: 엔비스카의 영혼

취업 준비로 요즘 코딩테스트를 준비하면서 블로그를 신경쓰지 못했다 ㅜㅜ.. 

그래서 블로그에 글도 올릴겸 좀 재미있는 문제와 개인적으로 어렵게 느껴졌던 문제들을 공유하기로 결심했다.

 

🎁 문제

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

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

• 기다리기
• a명 앞으로 가기 (앞에 최소 a명 있을 때)
• b명 앞으로 가기 (앞에 최소 b명 있을 때)

단, 한길이는 새치기에는 도가 텄기때문에, 모든 행동을 0초만에 할 수 있다.

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

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

 

ex) input: 5 1 2 // output: 2

 

📢 풀이

처음 문제를 보고 너무 쉽다고 생각했다. 그 이유는 N명의 사람 + 한길이 즉, N+1의 배열을 선언하고 가장 앞사람을 제거하면서 1초씩 늘리고 a 또는 b명 앞으로 갈 수 있을 때는 무조건 가는 형식으로 반복하면 되겠구나라고 생각했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void swap(vector<int>& v, int a, int b) {
    int temp = v[a];
    v[a] = v[b];
    v[b] = temp;
}
int main(void){
    int n, a, b;
    cin >> n >> a >> b;
    int av = max(a, b);
    int bv = min(a, b);
    vector<int> line;
    for (int i = 0; i <= n; i++) line.push_back(i);
    int time = 0;
    while (1) {
        line.erase(line.begin());
        time++;
        int cur = find(line.begin(), line.end(), n) - line.begin();
        if (cur - av >= 0)
            swap(line, cur - av, cur);
        else if (cur - bv >= 0)
            swap(line, cur - bv, cur);

        if (line[0] == n)break;
    }
    cout << time;
    return 0;
}

결과는 ....

이제서야 알게되었다.. 이 문제가 DP라는 것을 그래서 규칙을 찾고자 노력했다.

input이 5, 1, 2 해당 예제로 풀이를 진행해보겠다.

만약 N=5가 아니라 N=1인 상황에서는 답이 무엇일까? 

1, 2만큼 점프할 수 있어도 반드시 처음 1초는 동작해야하므로 1초가 지나고 앞사람이 없어지면 그 다음으로 한길이 차례이다. 그래서 정답은 1이다.

만약 N=2인 상황에서는 답이 무엇일까?

1초가 지난 후 두 사람이 남게되고 한길이는 마법을 사용할 수 있다. 이 때, a=1이므로 한 사람 앞으로 갈 수 있다. 그래서 정답은 1이다.

N=3의 경우에도 b=2이므로 두 사람 앞으로 갈 수 있어서 정답은 1이다.

그럼 마지막으로 N=4일 때는 정답이 무엇일까?

해당 그림을 통해 정답은 2라는 것을 확인할 수 있다. 이를 DP(Dynamic Programming) 관점에서 생각해보자.

일단은 한 사람씩 집에 가기 위해서는 +1초가 걸린다. 그러므로 기본 공식은 dp[i]=dp[i-1]+1 이 될 것이다. 

그런데 앞 사람의 수가 a 또는 b보다 크다면  한길이는 새치기를 할 수 있다. 

앞서 살펴본 예제로 N=2 인 경우를 예로 들어보자. 가장 먼저 새치기를 고려하지 않았을 때를 생각해보면

dp[0] = 0

dp[1] = 1

dp[2] = 2

이런식으로 한길이는 2초 후 젤 앞자리가 될 것이다. 그러나 한길이는 1칸 점프가 가능하다. 이를 고려해보면

if(2 - a - 1>=0) (-1을 해주는 이유는 자기자신을 제외한 사람 수를 기준으로 하기 때문)

dp[2] = min(dp[1], dp[2-a-1] + 1) 이런식으로 가설을 세워볼 수 있다. 또한 dp[2 -a - 1]에서 1을 더해준 이유는 새치기를 하기 전에 1초가 흘러야 하기 때문이다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000001];
int main() {
    int n, a, b;
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) dp[i] = 1000001;
    if (b > a) {
        int tmp = a;
        a = b; 
        b = tmp;
    }
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i - a - 1 >= 0) dp[i] = min(dp[i], dp[i - a - 1] + 1);
        if (i - b - 1 >= 0)   dp[i] = min(dp[i], dp[i - b - 1] + 1);

    }
    cout << dp[n];
}

 

📢 결론

사실 DP는 나도 아직 잘 모른다. DP는 최대한 많이 풀어봐야 할 것같다! 그리고 백엔드 개발은 JAVA로 진행하면서 코딩테스트는 왜 C++로 진행하는지 물어보는 사람도 있었다. 이유는 간단하다. C/C++을 가장 많이 사용해봤고 가장 잘할 수 있는 언어이기 때문이다. 하지만.. JAVA로 개발을 계속 진행할거라면 언젠가는 변경하는게 좋을..지도?