HackerRank [Recursion] The Power Sum /알고리즘 해커랭크

문제 주소 : https://www.hackerrank.com/challenges/the-power-sum/problem

The Power Sum | HackerRank

문제 : X값과 N값이 주어졌을때 X값을 자연수의 N승만큼 한 값을 합해 만들 수 있는 케이스의 수를 구하는문제

보기에 나오는 예를 보면 X가 100 N이 2로 주어졌을경우 자연수의 2승의 합으로 100을 만들 수 있는 경우는 10^2, 6^2+8^2, 1^2+3^2+4^2+5^2+7^2  이와같이 3가지 방법으로 표현이 가능하다

풀이

 1. 먼저 X루트 N을하면 어떤 값을 N승 했을 때 X보다는 작은 최대값을 구할 수 있다
   예) 위의 예시로 100루트 2라면 10이 나오고 수식을 계산할 자연수의 최대값은 10임을 알 수 있다

 2. X값을 N승 했을때 자연수를 제외하고 남는값이 0이면 딱 맞아 떨어진것이므로 정답의 케이스가 하나 추가된다

 3. 루트값을 구하고 자연수를 원래 X값에서 뺀 뒤 재귀함수를 통하여 이를 반복하되 사용한 숫자는 이미 사용되지 않도록 재귀함수에 파라미터로 넘겨준다
예시)
  * X가 100 N이 2이면 우선 100 루트2의 값은 자연수 10이고 남은 값이 없으므로 정답 케이스 하나 추가
  (최대의 자연수10)
  * 다음으로 100 - 9^2 승  => 남은 값 19 (여기서 X가 19 N이 2라고 정하고 재귀함수 동작)
  * 반복하여 1까지 내려갔는데 나머지가 0이 나오지 않음  
  * 최상단으로 빠져나와 100 - 8^2승 => 남는값 36 (여기서 X가 36 N을 2로 재귀함수 동작)
  * 36 루트 2는 6 남는값 없음 -> 카운트 증가
  * 최상단으로 나와서 100 - 7^2승 쭈욱끝까지 반복

 

답안

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the powerSum function below.
def powerSum(X, N, MaxVal):
    fRoot = X ** (1/N)
    nRoot = int(fRoot)
    if nRoot > MaxVal:
        nRoot = MaxVal

    nAnswer = 0
    
    for i in range(int(nRoot)):
        ResultVal = X - math.pow(nRoot-i, N)
        if ResultVal == 0:
            nAnswer += 1
            continue
        else: # ResultVal > 0:
            nAnswer += powerSum(ResultVal, N, nRoot-i-1)
    
    return nAnswer

if __name__ == '__main__':
    # fptr = open(os.environ['OUTPUT_PATH'], 'w') #VSCode로 컴파일 할 수 있도록 수정
    fptr = sys.stdout

    X = int(input())

    N = int(input())

    result = powerSum(X, N, X)

    fptr.write(str(result) + '\n')

    fptr.close()

 

느낀점

매번 재귀함수 문제는 풀면서도 긴가민가 하게 만든다
그리고 재귀로 풀면 내가 뭔가 알고리즘을 잘못만들어서 재귀로 하고있는건 아닌지
이대로 만들면 타임아웃이 나진 않을지 신경쓰이게 한다
이번 문제는 카테고리가 Recursion이였기에 좀 걱정이 덜했지만
다른 카테고리의 알고리즘 문제였다면 하면서도 많이 신경쓰였을것 같다 
실전에서 만약 아니라면 시간만 실컷쓰고 코드를 통으로 지워야 하는 경우가 있을것이라는 걱정때문인거 같다
경험이 쌓여서 노하우를 쌓는 방법밖엔 없지 않을까 싶다