c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q42 유리컵 속 물을 반으로

[문제]

용량이 A, B, C인 컵이 있다. (A > B > C, A, B, C는 정수)

A는 짝수이고, B와 C는 서로소이며, A = B + C를 만족한다.

제일 처음에는 A컵에만 물이 가득 담겨있다.

이제 컵에서 컵으로 물을 옮겨서 최종적으로 A컵에 물을 절반 (A / 2)만큼만 남기고 싶을 때,

이를 가능하게 하는 (A, B, C)의 가짓수는?

단, A는 10 이상, 100 이하이고, 물을 다른 컵으로 옮길 때는 컵이 모두 채워지거나 비워지거나 해야 한다.

(아래 그림에서 첫번째 케이스는 불가하고, 두번째, 세번째 케이스는 가능하다.)

[알고리즘]

규칙만 발견하면 간단하게 풀 수 있는 문제이다.

우선, A는 짝수이고, B와 C가 서로소라면 B와 C는 무조건 홀수여야 한다.

(B와 C가 짝, 홀이라면 A가 짝수가 될 수 없고, 짝, 짝이라면 서로소가 될 수 없다.)

이제 컵에서 컵으로 물을 옮겨가면서 각 컵의 물 양이 변하는 규칙을 한번 찾아본다.

 

예를 들어, A = 10, B = 7, C = 3이라고 한다.

맨 처음에는 2가지 방법이 가능하다. B컵에 물을 채우는 경우와 C컵에 물을 채우는 경우.

그러면 각각 컵의 물은 [3, 7, 0]과 [7, 3, 0]이 된다.

그 다음부터는 외길이다.

무슨 얘기나면,

[3, 7, 0]에서 다음 단계로 갈 수 있는 방법은 아래와 같이 3가지가 가능한데 첫번째, 세번째 2가지 경우는 무의미한 이동이므로 제외한다.

 

이런 식으로 다음 단계로 나아가면, 결국 각 단계마다 유의미한 물 옮기기 방법은 1가지만 가능하다는 것을 알 수 있다. 

아래 표는 A = 10, B = 7, C = 3일 때 각 컵의 물 양 변화를 나타낸 것이다.

위에서 말했듯이 맨 처음에만 A에서 B로 물을 옮기는 것과 A에서 C로 물을 옮기는 것 2가지가 가능하고, 그 다음부터는 외길이다.

위 표를 보면 패턴을 관찰할 수 있는데, (A컵 물의 양에만 집중하도록 한다.)

왼쪽 표에서는 A컵 물의 양이 10 -> 3 -> 6 -> 9 -> 2 -> 5 -> 8 -> 1 -> 4 -> 7로 변하는 것을 볼 수 있다.

즉, A컵 물의 양에 C만큼을 계속 더해 나가다가 넘치게 되면 B만큼 감소시킨 후 다시 C만큼 증가시키는 패턴이다.

오른쪽 표는 정 반대이다.

A컵 물의 양에 C만큼을 계속 빼 나가다가 0보다 작게 되면 B만큼을 더한 후 다시 C만큼 감소시키는 패턴이다.

일반화하면 A컵의 물의 양은 (오른쪽 표 기준)

A + mB - nC이다. (m, n은 양의 정수)

따라서 주어진 문제를 해결하기 위해서는 A + mB - nC = A / 2를 만족하는 A, B, C가 존재하는지 확인하면 된다.

A = B + C이므로 위 식을 정리하면

(1 + 2m)B = (2n - 1)C이다.

1 + 2m과 2n - 1은 모두 홀수이다. 즉, 문제 조건을 만족하는 B, C에 대해서 위 식을 만족하는 m과 n은 항상 존재하므로...

결국 이 문제는 다음과 같이 단순화할 수 있다.

A = B + C, B > C인 A, B, C에 대해서 B, C가 서로소인 홀수인 가짓수는? (단, A는 10이상 100이하 짝수)

 

이를 코드로 나타내면 아래와 같다.

#include <stdio.h>
#include <stdbool.h>

bool coprime(int x, int y);
int main() {
    int cnt = 0;
    for (int A = 10; A <= 100; A += 2) {
        for (int B = A - 1; B > A / 2; B -= 2) {
            int C = A - B;
            if (coprime(B, C) == true)
                cnt++;
        }
    }
    printf("cnt = %d\n", cnt);
}
bool coprime(int x, int y) {
    int min = x > y ? y : x;
    for (int i = 2; i <= min; i++)
        if (y % i == 0 && x % i == 0)
            return false;
    return true;
}

정답은 514가지.