[HackerRank] The Power Sum

# 정답 코드
def powerSum(X, N):
    # Write your code here
    def helper(target,power,num):
        if target == 0:
            return 1
        if target < 0 or num > math.sqrt(target):
            return 0
        # 현재 수를 포함하는 경우와 포함하지 않는 경우의 수를 재귀적으로 계산
        include = helper(target-num**power,power,num+1)
        exclude = helper(target,power,num+1)
        
        return include + exclude
    
    return helper(X,N,1)

이번 문제는 주어진 X값을 N제곱수로 만들 수 있는 경우의 수를 구하는 문제이다.

 

 

처음에 이 문제를 풀이했을 때는 X보다 작은 제곱수들을 모두 만들고, 조합을 사용하여 모든 경우의 수를 구해본 뒤 그 합이 X와 동일하면 count 해주는 방식으로 풀이하였다.

# 테스트케이스 1개 시간초과 코드
def gen_combination(arr,n): # 조합 구현 코드
    result = []
    if n == 0:
        return [[]]
    
    for i in range(len(arr)):
        element = arr[i]
        rest_arr = arr[i+1:]
        
        for c in gen_combination(rest_arr,n-1):
            result.append([element]+c)
            
    return result
    
def powerSum(X, N):
    power_list = []
    solution = [[]]
    count = 0

    i = 1
    while i**N <= X:
        power_list.append(i**N)
        i += 1

    for i in range(1,len(power_list)+1):
        solution += comb(power_list,i)

    for i in solution:
        if sum(i) == X:
            count += 1

    return count

하지만 1개의 테스트케이스에서 시간초과가 발생했고, 그 원인을 발견하지 못해 답안을 참고하였다.

 

정답코드의 풀이는 다음과 같다.

1. 만들고자 하는 값(target), 차수(power), 수(num)을 매개변수로 받는 또 다른 함수를 선언한다.
2. target이 0인 경우에는 재귀를 통해 경우의 수를 찾은 것이므로 1을 반환
3. target이 0보다 작아지거나 target의 제곱근이 num보다 작아지면 경우의 수가 존재하지 않으므로 0을 반환
4. target에서 현재 수(num)를 제곱한 수를 뺀 경우, 즉 현재 수를 포함하는 경우와 현재 수(num)를 제곱한 수를 빼지 않은 경우, 즉 현재 수를 포함하지 않는 경우를 모두 재귀함수에 넣어서 경우의 수를 더하고 반환한다.

이번 문제를 풀면서 재귀를 활용한 조합 구현을 배울 수 있었지만, 이번 문제에서 요구하는 바는 재귀함수를 사용하여 원하는 값을 구하는 것으로 보인다.

 

큰 문제를 해결하기 위해서 재귀함수를 사용해 작은 문제로 분할하여 풀기 위해서는 모든 경우의 수를 고려해야 한다는 점과, 모든 경우의 수를 고려하기 위해서는 return 조건과 분할 조건을 잘 생각해야 한다는 것을 배울 수 있었다 :)