[C/C++] 프로젝트 오일러 #88 Product-sum Numbers(단순 해결)

이 프로그램은 Project Euler 문제 #88, Product-sum Numbers 문제를 해결하기 위해 작성된 C 코드입니다. 이 문제는 “product-sum number”와 관련된 문제로, 숫자들의 곱과 합이 같은 여러 가지 조합을 찾는 것입니다.

 

product-sum numbers

 

문제 링크는 다음과 같습니다.

https://projecteuler.net/problem=88

 

다음은 코드의 각 부분을 설명합니다.

코드 분석

1. 상수 정의 및 배열 초기화

#define MAXK 12000
int minv[MAXK + 1];
int mcount = 0;

MAXK는 문제에서 요구하는 k 값의 최대 크기 (12000)를 정의한 것입니다. minv 배열은 k 값마다 최솟값인 n을 저장합니다. mcount는 찾아낸 값의 개수를 카운트합니다.

2. 재귀 함수 trav

bool trav(int n, int p, int s, int k, int c)

trav 함수는 재귀적으로 값을 계산하면서 n을 곱과 합이 같은 형태로 표현할 수 있는지를 탐색합니다.
• n: 현재 탐색 중인 수.
• p: 현재까지의 곱(product).
• s: 현재까지의 합(sum).
• k: 요소의 개수.
• c: 반복의 시작 지점으로, 중복되는 계산을 피하기 위해 설정합니다.
함수 동작:
• p == n일 때, k 값을 조정해 minv 배열에 저장할 값인지 확인합니다.
• minv[k]가 비어있다면 값을 저장하고, mcount를 증가시킵니다.
• 루프를 통해 조건을 만족하는 모든 i 값에 대해 재귀적으로 trav를 호출하여 탐색합니다.

3. 메인 로직 함수 solve1

void solve1()

이 함수는 문제의 답을 계산하는 메인 함수입니다.
• n 값을 4부터 증가시키면서, mcount가 MAXK-1에 도달할 때까지 반복합니다.
• 각 n 값에 대해 trav 함수를 호출하여 n을 나눌 수 있는 요소들이 곱과 합이 같아질 수 있는지 확인합니다.
• isFound가 true이면, 해당 n 값을 ans에 더합니다.
• 반복문이 끝나면 ans 값이 최종 결과가 됩니다.

4. 메인 함수

int main()

main 함수는 전체 프로그램의 실행 시간을 측정하고, solve1 함수를 호출하여 결과를 출력합니다.

코드 동작 요약

이 프로그램은 주어진 MAXK 값까지의 최소 n 값을 구합니다. 곱과 합이 같은 수를 찾기 위해 모든 조합을 탐색하면서, 각 k 값마다 최솟값 n을 기록해 ans에 누적하여 최종 결과를 출력합니다.

이 방식은 브루트 포스 방식으로 다양한 곱셈 조합을 계산하기 때문에 연산이 많고, mcount와 재귀 함수를 통해 탐색을 최적화하려고 합니다.

 

전체 소스는 다음과 같습니다.

//------------------------------------------------
//    Project Euler #88 - Product-sum Numbers
//        - by Aubrey Choi
//        - created at 2015-10-18
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

//#define    MAXK    12
#define    MAXK    12000

int minv[MAXK + 1];
int mcount = 0;

bool trav(int n, int p, int s, int k, int c)
{
    if (p == n)
    {
        k += n - s;
        if (k > MAXK) return false;
        if (minv[k]) return false;
        minv[k] = n;
        mcount++;
//        printf("(%d, %d)", k, n);
        return true;
    }
    bool isFound = false;
    for (int i = c; i <= n / p; i++)
    {
        if (n / p / i == 0) break;
        if (n%i) continue;
        isFound |= trav(n, p*i, s + i, k + 1, i);
    }
    return isFound;
}

void solve1()
{
    int ans = 0;
    for (int n = 4; mcount < MAXK - 1; n++ )
    {
        bool isFound = false;
        for (int i = 2; i*i <= n; i++ )
            isFound |= trav(n, i, i, 1, i);
        if (isFound) ans += n;
    }
    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);
}