[C/C++] 프로젝트 오일러 #109 Darts

프로젝트 오일러 문제 #109: “다트판 점수 계산”

이 문제는 다트 게임에서 점수를 계산하는 다양한 방법을 다루는 문제입니다. 다트 게임에서는 특정 규칙에 따라 점수를 계산하며, 이 문제에서는 가능한 점수 조합을 찾는 데 중점을 둡니다.

문제 요약

다트판에는 1부터 20까지의 숫자가 있으며, 각각의 숫자는 싱글, 더블, 트리플로 구분됩니다.
• 싱글(Single): 점수가 그대로 계산됩니다. 예: 20 -> 20점
• 더블(Double): 점수가 2배로 계산됩니다. 예: 20 -> 40점
• 트리플(Triple): 점수가 3배로 계산됩니다. 예: 20 -> 60점

또한, 다트판에는 불스아이(Bullseye)가 있으며, 이는:
• 싱글 불(Single Bull): 25점
• 더블 불(Double Bull): 50점입니다.

게임의 규칙상 마지막으로 던진 다트는 반드시 더블 영역에 맞아야 점수가 유효합니다. 예를 들어, 최종 점수가 50이라면, 마지막 다트는 반드시 “더블 불”이어야 합니다.

이 문제에서 목표는 주어진 최대 점수(99점 이하) 내에서 마지막 다트를 더블로 끝내는 모든 점수 조합의 수를 구하는 것입니다.

즉, 여러 번의 다트를 던져 원하는 점수를 달성할 수 있는 경우의 수를 찾는 문제로, 각 경우는 점수를 계산하는 순서에 따라 다른 조합으로 간주됩니다.

 

darts

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #109 - Darts
//        - by Aubrey Choi
//        - created at 2015-11-03
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

struct Counts
{
    int total;
    int below100;
    int hit6;
};

void traverse(Counts &counts, int slots[], int slot, int start)
{
    const int values[62] = 
    {
        101, 102, 103, 104, 105, 106, 107, 108, 109, 110,
        111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 125,
        201, 202, 203, 204, 205, 206, 207, 208, 209, 210,
        211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 225,
        301, 302, 303, 304, 305, 306, 307, 308, 309, 310,
        311, 312, 313, 314, 315, 316, 317, 318, 319, 320
    };

    if( slot <= 2 )
    {
        for( int i = 21; i < 42 ; i++ )
        {
            int score = 0;
            for( int s = 0 ; s < slot ; s++ )
                score += (slots[s]/100)*(slots[s]%100);
            score += (values[i]/100)*(values[i]%100);
            counts.total++;
            if( score < 100 ) counts.below100++;
            if( score == 6 ) counts.hit6++;
        }
    }
    if( slot == 2 ) return;
    for( int i = start ; i < 62 ; i++ )
    {
        slots[slot] = values[i];
        traverse(counts, slots, slot+1, i);
    }
}

void solve1()
{
    Counts counts = { 0, 0, 0 };
    int slots[3];

    traverse(counts, slots, 0, 0);

    printf("Ans = %d (total=%d, hit6=%d)\n", counts.below100, counts.total, counts.hit6);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

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

 

위 코드는 프로젝트 오일러 #109 문제를 해결하기 위해 작성된 프로그램입니다. 이 코드는 다트 점수를 계산하고 특정 조건(100점 미만, 점수 6, 등)을 만족하는 경우의 수를 찾습니다. 각 함수와 코드 블록을 설명하겠습니다.

구조체 정의: Counts

struct Counts
{
    int total;      // 전체 경우의 수
    int below100;   // 점수가 100점 미만인 경우의 수
    int hit6;       // 점수가 정확히 6점인 경우의 수
};

• 결과를 저장하는 구조체입니다.
• 전체 시도(total), 점수 조건별 개수(below100, hit6)를 추적합니다.

값 배열: values

const int values[62] = 
{
    101, 102, ..., 320
};

• 값 형식: 세 자리 숫자에서 첫 번째 자리는 점수 배수(1=싱글, 2=더블, 3=트리플), 뒤의 두 자리는 해당 점수입니다.
• 예: 101은 싱글 1점, 215는 더블 15점, 318은 트리플 18점.

재귀 함수: traverse

void traverse(Counts &counts, int slots[], int slot, int start)

• 점수 조합을 순회하며 조건을 만족하는 경우의 수를 계산합니다.

매개변수

1. Counts &counts: 현재까지 계산한 결과를 저장합니다.
2. int slots[]: 현재 다트 점수 조합을 저장합니다.
3. int slot: 현재 다트를 몇 번 던졌는지 나타냅니다(0~2).
4. int start: 탐색 시작 위치입니다(중복 방지를 위해).

코드 흐름

1. 종료 조건 (3개 이하 다트를 던진 경우만 탐색):

if( slot <= 2 )

• 21~41 범위의 values 값(더블 영역)을 반복합니다.
• 점수(score)를 계산:

for( int s = 0 ; s < slot ; s++ )
    score += (slots[s]/100)*(slots[s]%100);
score += (values[i]/100)*(values[i]%100);

• values의 배수와 점수를 곱하여 합산.

• 조건에 맞는 경우의 수를 증가:

counts.total++;
if( score < 100 ) counts.below100++;
if( score == 6 ) counts.hit6++;

2. 재귀 호출:

if( slot == 2 ) return;
for( int i = start ; i < 62 ; i++ )
{
    slots[slot] = values[i];
    traverse(counts, slots, slot+1, i);
}

• 현재 점수(values[i])를 선택하고 다음 다트를 계산합니다.

메인 함수: solve1

void solve1()

• Counts 구조체와 slots 배열을 초기화합니다.
• traverse 함수를 호출하여 모든 조합을 탐색합니다.
• 최종 결과를 출력합니다:

printf("Ans = %d (total=%d, hit6=%d)\n", counts.below100, counts.total, counts.hit6);

전체 요약

1. values 배열을 통해 모든 다트 점수 조합을 탐색합니다.
2. 재귀적으로 조합을 생성하고, 조건을 만족하는 경우의 수를 카운트합니다.
3. 총 경우의 수(total), 100점 미만 경우의 수(below100), 점수 6의 경우의 수(hit6)를 계산합니다.
4. 결과를 출력하며 실행 시간을 표시합니다.