왕자 대 용 알고리즘 문제

전에 지인으로부터 알고리즘 문제를 하나 받았습니다. 쉽게 풀 수 있을 것 같았지만 특정한 경우 필요한 수식의 답을 구할 수학 실력이 없어서 대강의 코드만 만들어 놓고 거의 포기 상태였습니다.

어제 서버의 작업 공간에 있는 코드들을 정리하다 풀다만 코드를 다시 보았지만 역시 똑같은 어려움에 봉착했습니다. 이건 제가 알고있는 지식으로는 못 푼다고 결론을 내리고 KLDP에 질문을 올렸습니다. 하루도 안 되서 답변이 달렸고 문제를 풀 수 있었습니다.

우선 문제부터 좀 보고 이야기를 계속 해 나가기로 하겠습니다.

왕자와 용이 목숨을 건 대결을 벌입니다. 왕자와 싸우는 용의 머리는 n 개입니다. 왕자는 마법검을 두개 가지고 있는데, 하나는 c1개의 용 머리를 또 다른 하나는 c2개의 용 머리를 자를 수 있습니다.

두개의 마법검으로 용 머리를 모두 자르면 왕자가 승리합니다. 단, 용 머리를 마법검으로 잘랐는데 모든 머리를 자르지 못 하면 c1 마법검을 썼을 경우 g1, c2 마법검을 썼을 경우 g2 개만큼의 머리가 다시 생겨납니다.

마법검은 자를 머리의 개수가 모자라지 않을 경우에만 사용 할 수 있습니다. 즉, 머리 5개를 자를 수 있는 마법검은 머리가 3개 남은 용에게 사용 할 수 없습니다.

만약 남은 용의 머리 개수가 c1 - 1 이거나 c2 - 1인 경우 왕자는 자신의 머리를 포함해서 마법검을 사용 할 수 있고, 이 경우 용과 왕자 모두 죽게 되어 승패는 비깁니다.

입력 파일을 통해서 n, c1, g1, c2, g2 값이 주어지고, 승자를 출력하는 프로그램을 만들면 됩니다.

입력
1
2
3
20 7 1 8 5
3 4 1 2 2
100 102 0 103 0
출력
1
2
3
PRINCE
DRAW
DRAGON

직접 문제를 풀어보시고 제 풀이와 한 번 비교를 부탁드립니다.

왕자 대 용 알고리즘 문제 입력 데이터 파일 다운로드

풀이

우선 제가 KLDP에 올린 질문으로부터 얻은 답은 문제를 ‘확장 유클리드 호제법‘을 사용해서 풀면 된다는 것이었습니다. 더 정확히는 ‘디오판토스 방정식‘입니다. 자세한 설명은 각각 링크를 참고 해주시면 감사하겠습니다.

막상 디오판토스 방정식을 이용해서 문제를 푸니 아주 특별한 경우를 빼고는 예외적인 처리조차 할 필요가 없더군요. 일단 전 이렇게 이 문제를 생각했습니다.

왕자가 승리하는 경우 마지막에 용의 머리는 반드시 c1 또는 c2개가 남아있어야 합니다. 그렇다면 마법검을 사용을 해서 변화되는 용의 머리 개수의 곱의 합으로 마지막 일격을 뺀 용의 머리 개수를 만들 수 있다면 용을 죽일 수 있다고 보았습니다. 즉 아래와 같은 수식으로 바꾸었습니다.

$$ n - c1 = a(c1 - d1) + b(c2 - d2) $$ $$ n - c2 = a(c1 - d1) + b(c2 - d2) $$

이 식을 만족시키는 정수 a, b가 존재한다면 용을 죽일 수 있습니다. 이런 정수 a, b의 존재와 일반해를 구하는 것이 ‘디오판토스 방정식’이더군요. 제가 이 문제를 풀 수 없었던 것이 이런 것을 전혀 모르고 있었기 때문이었구요. 학부 때 정수론을 배우지 않은 것은 후회되었습니다.

그리고 비기는 경우는 용의 머리 갯수에 왕자의 머리 갯수(1!!)를 더한 값을 만족시키는 a, b가 존재하면 된다고 생각했습니다. 물론 왕자가 이길 수 있는 경우에는 비길 수 있더라도 이기는 결과를 우선으로 했습니다.

$$ n + 1 - c1 = a(c1 - d1) + b(c2 - d2) $$ $$ n + 1 - c2 = a(c1 - d1) + b(c2 - d2) $$

이 외에도 용의 머리 갯수가 0이하인 경우라던지 등의 예외에 대한 처리를 조금 추가해주는 것으로 풀이 소스 코드를 만들 수 있었습니다.

일단 문제는 풀었지만 코드 골프처럼 정답인지 여부를 확인 할 수 있는 길이 없기 때문에 올바르게 풀었다는 확신은 없는 상태입니다.

이 문제를 푸셨다면 제 이메일로 출력 파일이나 소스 코드를 보내주시면 비교하여 정답을 확인하는데 도움이 될 것 같습니다. 꼭 좀 도움 부탁드립니다.

끝으로 제가 푼 소스 코드를 올립니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


#! /usr/bin/perl

use strict;
use warnings;

sub gcd {
    my $a = shift;
    my $b = shift;

    my $c;
    do {
        $c = $a % $b;
        $a = $b;
        $b = $c;
    } while ( $c != 0 );

    return $a;
}

sub slash {
    my $a = shift;
    my $b = shift;
    my $c = shift;

    return 1 if $c <= 0;
    return ($b > 0 && $c % $b == 0) ? 1 : 0 if $a == 0;
    return ($a > 0 && $c % $a == 0) ? 1 : 0 if $b == 0;

    return ($c % gcd($a, $b) == 0) ? 1 : 0;
}

sub winner {
    my ($n, $c1, $d1, $c2, $d2) = @_;

    # 마법검으로 잘랐을 때 줄어드는 용 머리 갯수
    my $h1 = $c1 - $d1;
    my $h2 = $c2 - $d2;

    # 용 머리만 자르는 경우
    my $n1 = $n - $c1;
    my $n2 = $n - $c2;
    return 'PRINCE' if ($n1 >= 0 && slash($h1, $h2, $n1)) || ($n2 >= 0 && slash($h1, $h2, $n2));

    # 용과 왕자 머리를 모두 자르는 경우
    $n1 = $n + 1 - $c1;
    $n2 = $n + 1 - $c2;
    return 'DRAW' if ($n1 >= 0 && slash($h1, $h2, $n1)) || ($n2 >= 0 && slash($h1, $h2, $n2));

    # 용 승리
    return 'DRAGON';
}

my $fh;
open $fh, '<', 'input.txt' or die;
while ( <$fh> ) {
    chomp;
    my @data = split /\s+/;
    print winner(@data), "\n";
}
close $fh;

풀이#

풀이