[백준 1697번/C언어] 숨바꼭질 풀이

백준 1697번 문제를 풀어보았습니다. 

백준 1697번: https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

 

 

문제 내용은 다음과 같습니다.

 

 

 

 

저는 이 문제를 동적계획법을 적용하는 문제라고 생각하고 접근했습니다. 결과적으로 보통 제가 접근했던 동적계획법 문제들처럼 배열을 사용하지는 않았지만, 점화식을 활용해 문제를 쪼개서 접근했다는 점에서는 DP를 활용했다고 말할 수 있을 것 같습니다. 제가 처음에 이 문제를 동적계획법을 사용해야겠다고 생각한 이유는 백준 문제 중 1로 만들기라는 문제와 유사했기 때문입니다. 결과적으로 완전히 같은 방식을 사용한 것은 아니지만, 그때 문제를 풀었던 것을 어느 정도 활용해 접근했습니다. 1로 만들기 문제 풀이에 대한 제 포스팅은 아래 링크에서 확인하실 수 있습니다. 

https://programming-diary-ina.tistory.com/10

[백준 1463번/C언어] 1로 만들기, 동적계획법으로 풀이

 

 

 

 

 

 코드 설명에 앞서, 제가 문제 풀이에서 사용한 점화식을 먼저 설명해드리겠습니다. 저는 점화식을 세울 때 문제에서 제시한 대로 N이 K로 다가간다기보다는 K가 N으로 다가가는 방향으로 생각했습니다. 그래야 K가 2의 배수인지 판단하여 한 칸을 이동해야 할지, 순간이동을 해야 할지 결정하기가 쉽다고 생각했기 때문입니다. 그래서 재귀함수의 인자를 K로 두어 K값을 바꿔주면서, K값을 2로 나누는 것과 1을 더하고 빼는 것만 활용하여 어떻게 효율적으로 N값으로 만들 수 있는가로 생각하면서 문제를 풀었습니다. 

 

[case1: K - N <= 1]  F(K) = abs(K - N)
[case2: K % 2 == 0]  F(K) = Min((K - N), F(K / 2) + 1)
[case3: K % 2 == 1]  F(K) = Min(F(K-1), F(K+1)) + 1

 

위 박스에 나와있는 식들이 제가 각 경우 별로 세운 점화식입니다. 우선 저는 케이스를 세 개로 나누었습니다. 첫번째는 K-N이 1보다 작거나 같은 경우입니다. 이 경우는 세 가지 경우를 염두에 두고 만든 케이스인데요, K가 N보다 작은 경우, K와 N이 같은 경우, 그리고 둘 간의 차이가 하나밖에 나지 않는 경우입니다. K가 N보다 작은 경우에 우리는 순간이동을 선택할 수 없고, 한 칸씩 줄여나가서 K에 도달해야 합니다. 따라서 이 경우에는 K와 N의 차가 곧 이동 횟수가 될 수밖에 없습니다. 둘이 같은 경우에는 이동할 것 없이 0이 답이 되므로, 또 둘 간의 차를 적용해도 문제가 없습니다. 마지막으로 둘 간의 차이가 하나밖에 나지 않는 경우에는 순간이동할 필요 없이 그냥 한 번만 이동하여 도달하면 됩니다. 따라서 이 세 가지 경우 모다가 첫 번째 케이스를 통해 해결될 수 있습니다. 

 두 번째는 K가 2의 배수인 경우입니다. 이 때는 순간이동을 별도의 처리 없이 적용 가능합니다. 그래서 그냥 한 칸씩 이동하는 방법(K - N)과 순간이동을 적용하는 방법(F(K/2) + 1) 중 더 유리한 쪽을 선택하면 됩니다. 

 세 번째는 K가 2의 배수가 아닌 경우입니다. 이 경우에는 바로 순간이동을 할 수 없습니다. 따라서 1을 더하여 2의 배수로 만들어 준 후 다시 처리하는 방법과 1을 빼서 2의 배수를 만들어주는 방법 중 더 유리한 쪽을 선택하고, 1을 더해주면 (+1 혹은 -1을 해서 함수에 넣었기 때문에 한번의 이동을 한 것) 됩니다. 

 

 

 

사실 점화식만 나오면 코드는 구현하기 어렵지 않습니다. 메인 함수에서 N과 K값을 입력받아주고, 해당 값을 넣어 countSecond()라는 재귀함수를 불러주어 앞서 설명한 점화식을 바로 적용해 주면 됩니다.

 countSecond() 함수에서 가장 처음에 나오는 if문이 앞선 점화식에서 언급한 case1입니다. 절댓값을 구현해주기 위해서 if문을 활용했습니다. <stdlib.h> 헤더에 abs() 함수를 사용해 줘도 됩니다. 그리고 두 번째 if 문은 case2에 해당하고 else문은 case3에 해당됩니다. 재귀를 두 번 실행하지 않게 하기 위해 temp 변수들을 사용하여 값을 저장해 준 후 비교해 주었습니다. 

#include <stdio.h>

int countSecond(int N, int K) {
    if (K - N <= 1) {
        if (K - N >= 0) return (K - N);
        else return (N - K);
    }
    
    if (K % 2 == 0) {
        int temp = 1 + countSecond(N, K/2);
        if ((K - N) < temp) return (K-N);
        else return temp;
    } else {
        int temp1 = countSecond(N, K-1);
        int temp2 = countSecond(N, K+1);
        if (temp1 > temp2) return (temp2 + 1);
        else return (temp1 + 1);
    }
}

int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    
    printf("%d", countSecond(N, K));
}