[HackerRank] The Power Sum

https://www.hackerrank.com/challenges/the-power-sum/problem 

The Power Sum | HackerRank

Algorithms > Recursion

 

정수 X와 N이 주어지고, 어떤 수들의 N제곱의 합이 X와 같아지는 경우의 수를 찾는 문제다.

 

 

코드

int powerSum(int X, int N, int base, int sum) {
    int temp = pow(base, N);
    if (sum + temp == X) return 1;
    else if (sum > X || temp > X) return 0;
    else {
        return powerSum(X, N, base + 1, sum + temp) + powerSum(X, N, base + 1, sum);
    }
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    int X = parse_int(ltrim(rtrim(readline())));

    int N = parse_int(ltrim(rtrim(readline())));

    int result = powerSum(X, N, 1, 0);

    fprintf(fptr, "%d\n", result);

    fclose(fptr);

    return 0;
}

 

설명

powerSum 함수는 X, N, base(밑), sum(현재 어떤 수들의 N제곱의 합)을 매개변수로 가진다.

temp 변수에 현재 base^N의 값을 저장한다.

만약 지금까지의 합과 temp의 합이 X라면 조건을 만족하므로 1을 리턴한다.

만약 sum이 X보다 크거나 temp가 X보다 크면 조건을 벗어나므로 0을 리턴한다.

아직 값이 X에 도달하지 못했다면 base와 sum의 값을 조절해 재귀호출하고 더하여 리턴한다.

모든 계산이 끝나면 결과적으로 main 함수에서 주어진 조건을 만족하는 경우의 수를 result 변수에 담을 수 있게 된다.