스승님 찾기( BOJ 15979 )

문제 : https://www.acmicpc.net/problem/15979

15979번: 스승님 찾기

 

문제 파악하기

(0, 0)에서 (M, N)까지 이동하는데 필요한 순간이동 횟수를 구하는 문제입니다. 순간이동은 항상 현재 좌표에서 볼 수 있는 좌표로 이동할 수 있습니다. 떠올릴 수 있는 가장 간단한 방법은 최대공약수를 구하는 것입니다. 입력된 좌표값 (M, N)의 최대공약수를 구하면 (0, 0)에서 해당 숫자까지 이동하는 최단 직선 거리로 이동하는 순간이동 횟수를 구할 수 있습니다. 하지만 이 방법은 아쉽게도 반례가 있습니다. 만약 (3, 3)으로 이동하려면 어떻게 해야할까요?

 

(3, 3)으로 이동하는 방법을 간단하게 생각해보면 (1, 1)과 (2, 2)를 거쳐서 이동하는 총 3번 순간이동하는 방법을 떠올릴 수 있으며, 이 경로는 두 수의 최대공약수를 구해서 발견한 최단 직선 거리입니다. 하지만 (3, 3)으로 이동하는 최단 경로는 바로 (1, 2)를 거쳐서 (3, 3)으로 이동하는 총 2번 순간이동 하는 방법입니다. 이렇듯 문제를 잘 분석해보면 특징을 발견할 수 있습니다.

 

문제 해결하기

순간이동은 항상 해당 점의 좌표가 보이면 가능하다고 했습니다. 이 점을 활용하면 어떤 점이든 최대 2번의 순간이동으로 모든 점에 도달할 수 있습니다. 만약 (M, N)으로 이동하고 싶다면 (M-1, 1) 혹은 (1, N-1)로 순간이동합니다. 그리고 (M, N)으로 바로 순간이동하면 됩니다. 이 방법은 모든 좌표에서는 다음 x좌표 혹은 다음 y좌표에 해당하는 모든 점을 볼 수 있다는 점을 활용한 방법입니다. 이렇듯, 모든 문제에서 적용되지 않지만 특별한 문제에서 적용되는 방법을 에드 훅이라고 말합니다.

 

따라서, 우리는 어떤 좌표값이든 최대 2번 이내의 순간이동으로 원하는 위치로 이동할 수 있다는 걸 파악했습니다. 이 점을 활용하여 입력된 좌표값 M과 N의 최대공약수를 구한 다음, 2번보다 많은지 적은지 확인하면 문제를 해결할 수 있습니다. 단, 음수의 모듈러 연산은 양수일 때와 다르게 나올 수 있기에 모든 숫자를 양수로 만들고 진행해야 합니다.

 

소스코드

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int N, M, g;
 
int gcd(int a, int b) {
    if(a == 0) return b;
    else if(b == 0) return a;
    else return gcd(b, a%b);
} 
 
int main() {
    scanf("%d %d", &M, &N);
    if(N<0) N = -N;
    if(M<0) M = -M;
 
    g = min( gcd(M, N), 2 );
 
    printf("%d", g);
}
/*
3 3
ans: 2
>> (0, 0) > (1, 4) > (3, 3)
*/

후기

최대공약수와 관련된 문제로, 처음 풀 때 재미있게 풀었습니다. 최대공약수를 구하는 방법을 배운 학생에게 심화 문제로 추천할 만한 문제라고 생각합니다.