[C/C++] 프로젝트 오일러 #90 두개의 주사위로 제곱수 만들기(전체 검색)

프로젝트 오일러 #90번 문제는 “두 개의 주사위로 제곱수를 만들기”라는 제목을 가지고 있습니다. 문제의 요약은 다음과 같습니다.

1. 두 개의 6면체 주사위 세트를 사용하여 숫자 쌍을 만들어 특정한 제곱수를 표현하려고 합니다.
2. 각 주사위는 0에서 9 사이의 숫자 중 6개를 선택하여 각 면에 새길 수 있습니다.
3. 두 주사위를 굴려 나온 숫자 조합으로 제곱수 1, 4, 9, 16, 25, 36, 49, 64, 81을 표현해야 합니다.
• 예를 들어, 01은 1의 제곱, 49는 7의 제곱을 의미합니다.
4. 숫자 6과 9는 서로 교환 가능하다고 가정합니다.

목표: 두 주사위에서 선택할 수 있는 숫자 조합을 정하여 위의 모든 제곱수를 표현할 수 있는 경우의 수를 계산하는 것입니다.

이 문제는 조합론과 경우의 수를 활용하여 해결할 수 있으며, 주사위에 새길 숫자의 모든 가능한 조합을 고려하는 것이 핵심입니다.

 

cube digit pairs

 

제가 문제를 풀기 위해서 작성한 코드입니다.

//------------------------------------------------
//    Project Euler #90 - Cube Digit Pairs
//        - by Aubrey Choi
//        - created at 2015-10-20
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

void solve1()
{
    const int s[9][2] = { 1, 2, 1, 16, 1, 576, 2, 576, 4, 32, 8, 576, 16, 576, 576, 16, 256, 2 };
    static int pattern[1000], t;
    int pcount = 0;

    for (int a = 0; a < 10; a++)
    {
        t = 1<<a;
        for (int b = a + 1; b < 10; b++)
        {
            t |= 1 << b;
            for (int c = b + 1; c < 10; c++)
            {
                t |= 1<<c;
                for (int d = c + 1; d < 10; d++)
                {
                    t |= 1<<d;
                    for (int e = d + 1; e < 10; e++)
                    {
                        t |= 1<<e;
                        for (int f = e + 1; f < 10; f++)
                        {
                            t |= 1<<f;
                            pattern[pcount++] = t;
                            t &= ~(1<<f);
                        }
                        t &= ~(1 << e);
                    }
                    t &= ~(1 << d);
                }
                t &= ~(1 << c);
            }
            t &= ~(1 << b);
        }
    }

    printf("pcount = %d\n", pcount);

    int ans = 0;
    for (int i = 0; i < pcount - 1; i++)
    {
        for (int j = i + 1; j < pcount; j++)
        {
            bool isGood = true;
            for (int k = 0; k < 9; k++)
            {
                if (((pattern[i] & s[k][0]) && (pattern[j] & s[k][1])) || ((pattern[i] & s[k][1]) && (pattern[j] & s[k][0]))) continue;
                isGood = false;
                break;
            }
            if (isGood)    ans++;
        }
    }

    printf("Ans = %d\n", ans);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

이 코드는 Project Euler #90 - Cube Digit Pairs 문제를 해결하기 위한 프로그램입니다. 주사위의 숫자 조합을 통해 제곱수를 만드는 경우의 수를 계산하는 방식입니다. 주요 구조와 기능을 단계별로 설명하겠습니다.

주요 개념

1. 패턴과 비트마스크: 각 주사위의 6개 숫자 선택을 비트마스크로 표현합니다.
• 비트마스크 t는 각 숫자를 비트로 표현해 선택된 숫자를 저장합니다.
• 예를 들어, 숫자 0부터 9 중 하나를 선택하면, 10비트 중 해당 숫자 위치의 비트를 1로 설정하여 선택을 나타냅니다.
2. 제곱수 쌍 조건 확인: s 배열은 필요한 제곱수를 비트로 나타낸 형태입니다. 여기서는 제곱수를 표현하기 위해 (s[k][0], s[k][1]) 쌍으로 주사위의 조합이 필요한 숫자를 지정해 두었습니다.

코드 설명

void solve1()
{
    const int s[9][2] = { 1, 2, 1, 16, 1, 576, 2, 576, 4, 32, 8, 576, 16, 576, 576, 16, 256, 2 };
    static int pattern[1000], t;
    int pcount = 0;

• s 배열은 문제에서 요구하는 제곱수 쌍을 비트로 표현합니다.
• 예를 들어, s[0] = {1, 2}는 숫자 1과 2를 쌍으로 나타내는 것을 의미합니다.
• pattern 배열은 주사위에 새길 수 있는 모든 가능한 숫자 조합을 비트마스크로 저장하기 위한 배열입니다.
• pcount는 가능한 숫자 조합의 개수를 카운트하는 변수입니다.

    for (int a = 0; a < 10; a++)
    {
        t = 1<<a;
        for (int b = a + 1; b < 10; b++)
        {
            t |= 1 << b;
            for (int c = b + 1; c < 10; c++)
            {
                t |= 1<<c;
                for (int d = c + 1; d < 10; d++)
                {
                    t |= 1<<d;
                    for (int e = d + 1; e < 10; e++)
                    {
                        t |= 1<<e;
                        for (int f = e + 1; f < 10; f++)
                        {
                            t |= 1<<f;
                            pattern[pcount++] = t;
                            t &= ~(1<<f);
                        }
                        t &= ~(1 << e);
                    }
                    t &= ~(1 << d);
                }
                t &= ~(1 << c);
            }
            t &= ~(1 << b);
        }
    }

• 이 부분은 모든 가능한 주사위 숫자 조합을 생성하는 부분입니다.
• 0부터 9까지의 숫자 중 6개의 숫자를 선택하고, 그 조합을 비트마스크 t로 표현합니다.
• t |= 1 << X 구문은 숫자 X를 비트마스크에 추가합니다.
• t &= ~(1 << X) 구문은 숫자 X를 비트마스크에서 제거합니다.
• 각 조합이 pattern 배열에 저장되고, pcount는 총 조합 수를 카운트합니다.

    printf("pcount = %d\n", pcount);

• pcount는 생성된 가능한 숫자 조합의 개수를 출력합니다.

    int ans = 0;
    for (int i = 0; i < pcount - 1; i++)
    {
        for (int j = i + 1; j < pcount; j++)
        {
            bool isGood = true;
            for (int k = 0; k < 9; k++)
            {
                if (((pattern[i] & s[k][0]) && (pattern[j] & s[k][1])) || ((pattern[i] & s[k][1]) && (pattern[j] & s[k][0]))) continue;
                isGood = false;
                break;
            }
            if (isGood)    ans++;
        }
    }

• 이중 for문을 사용하여 서로 다른 두 주사위 조합 (i, j)를 선택하고, 이 조합이 문제에서 요구하는 모든 제곱수 쌍을 표현할 수 있는지 확인합니다.
• isGood 변수를 통해 조건이 만족되는지 확인하고, true 상태를 유지하면 ans를 증가시킵니다.

    printf("Ans = %d\n", ans);

• 가능한 조합의 총 개수 ans를 출력합니다.

main 함수

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

• main 함수는 solve1() 함수를 호출하여 문제를 풀고, 경과 시간을 출력합니다.