[Recursion] The Power Sum

난이도: ★★★☆☆ • solved on: 2025-12-02

---

문제 요약

• 문제 유형: DFS, 백트래킹, 재귀
• 요구사항: X를 N제곱수들의 합으로 나타내는 모든 고유 조합(unique combinations) 개수를 구해야 한다.

이 문제는 혼자서 풀어보려다 실패해 구글링을 통해 확인한 문제이다. 체감상 평점 3~3.5 정도의 문제.

---

사용 개념

1. 자료구조

   • 재귀 호출 스택
   • 불변 정수 상태값

2. 알고리즘/기법

   • DFS(Depth-First Search)
   • 백트래킹(backtracking)
   • 메모이제이션(optional)

3. 핵심 키워드

   • 조합(combination)
   • 제곱수 / N제곱수
   • 탐색 범위 제한(pruning)

---

내 풀이 분석

1. 접근 방식 요약

• i^N을 하나 선택하고, 남은 값 X - i^N이 제곱수인지 확인하는 방식으로 접근함.
• 즉, “$X = a^N + b^N$ 형태인지”만을 검사하는 구조였음.

2. 한계점

(1) 두 항($a^N + b^N$)까지만 고려되는 구조적 한계

문제는 X를 3개, 4개… 여러 개의 N제곱수 합으로 표현할 수 있어야 한다.
그러나 기존 접근은:

X = i^N + j^N  (두 항 구조)

형태만 검사하므로,

X = 1^N + 2^N + 3^N
X = 4^N + 1^N + 1^N

같은 3항 이상의 조합을 전혀 고려할 수 없다.

(2) 재귀가 ‘다음 숫자 범위’를 유지하지 않음 → 조합 중복 발생

powerSum(i, N) 같은 구조는 “남은 값”이 아닌, “다음 숫자 후보”를 의미하지 않는다.
즉,

• 1을 사용한 후 다시 1을 사용하는 일이 구조적으로 가능해짐
• 조합이 아닌 순열(permutation)에 가까운 구조로 흐르게 됨

(3) 제곱수 판별 방식이 문제 목적과 부합하지 않음

문제 요구는 '남은 값을 제곱수 1개로 표현할 수 있는지' 여부가 중요하지 않으며,
“여러 개의 제곱수들의 합으로 만들 수 있는지”를 모두 탐색해야 한다.

즉, “루트가 정수인지”는 문제 해결에 도움이 되지 않는 조건이다.

---

개선된 풀이 – 방법 1: DFS + 백트래킹

아이디어 핵심

• $i^N$ 을 하나 선택한다.

• $X - i^N$ 에 대해 다음 숫자 (i+1)부터 다시 탐색한다.

• 조합 중복을 막기 위해 “오름차순”으로만 선택한다.

• X가 0이 되면 1개의 valid 조합을 찾은 것이다.
  (이전의 숫자의 합이 곧 X가 된다는 의미이므로)

풀이 흐름

dfs(남은 값, 현재 숫자):
    if 남은 값 == 0:
        return 1
    
    if 남은 값 < 0:
        return 0
    
    count = 0
    for i from 현재 숫자 to max:
        power = i^N
        if power > 남은 값:
            break
        count += dfs(남은 값 - power, i+1)
    
    return count

---

코드

방법 1: DFS + 백트래킹

public static int powerSum(int X, int N) {
    return dfs(X, N, 1);
}

private static int dfs(int remain, int N, int num) {
    int p = (int) Math.pow(num, N);
    
    if (p > remain) return 0;
    if (p == remain) return 1;

    // num을 쓰지 않고 다음 숫자로 넘어가는 것과,
    // num을 포함해 조합을 만드는 두 경우를 모두 탐색
    return dfs(remain - p, N, num + 1) + dfs(remain, N, num + 1);
}

---

개선된 풀이 – 방법 2: DFS + 메모이제이션 (DP)

방금 풀이에서 재귀 과정을 수행하는 중 동일한 remain과 num 조합이 반복된다. 따라서 아래와 같은 DP 캐싱이 가능하다:

dp[remain][num] = remain을 num 이상의 숫자로 만들 수 있는 조합 수

코드

import java.util.*;

public class Solution {
    static Map<String, Integer> memo = new HashMap<>();

    public static int powerSum(int X, int N) {
        return dfs(X, N, 1);
    }

    private static int dfs(int remain, int N, int num) {
        String key = remain + "," + num;
        if (memo.containsKey(key)) return memo.get(key);

        int p = (int) Math.pow(num, N);
        if (p > remain) return 0;
        if (p == remain) return 1;

        int result = dfs(remain - p, N, num + 1) + dfs(remain, N, num + 1);
        memo.put(key, result);
        return result;
    }
}

---

시간·공간 복잡도

방법 1: 순수 DFS + 백트래킹

• 시간 복잡도: O(M)
  (M은 가능한 조합의 수. 최악은 최대 depth D에 대해 $2ᴰ$ 정도의 분기)
• 공간 복잡도: O(D) (재귀 깊이)

방법 2: DFS + 메모이제이션

• 시간 복잡도: O(X × √X) 정도까지 감소
  (remain과 num 쌍의 상태 수가 제한됨)
• 공간 복잡도: O(X × √X) (메모 저장)

---

어려웠던 점

• “$X$에서 $i^N$을 하나 빼고 남는 값이 또 제곱수인가?”만 고려한 방식이 문제 요구를 충족시키지 못함.

  • 처음에는 두수의 합 -> N수의 합으로 확장하며 접근하려 했지만 확장 과정이 굉장히 어려웠기에 이 접근이 맞지 않다 판단했다.

• 조합 구조를 고려하려면 탐색 순서와 범위 관리 (시작 숫자 제약)가 필수임을 깨닫기까지 시간이 걸림.

• 처음의 풀이는 재귀가 “두 항까지만 검사하는 구조”라 깊은 탐색이 전혀 이뤄지지 않았음.

---

배운 점 및 팁

• 조합 문제는 대부분 오름차순 선택 + 백트래킹으로 풀 수 있다.
• 재귀에서 “다음 후보 번호”를 넘기는 것은 중복 방지에 매우 중요하다.
• 수학적 성질 (제곱수 판별 등)을 억지로 결합하면 문제 원래 요구와 맞지 않아 오히려 로직이 꼬일 수 있다.

---

참고 및 링크

• 문제 링크:
  https://www.hackerrank.com/challenges/the-power-sum/problem
• 참고 자료: 없음

---

추가 연습 문제 (GPT 추천)

• 비슷한 유형:

  • Perfect Powers (BOJ 2417)
  • Subset Sum (BOJ 1182)

• 확장 문제:

  • Sum of N powers – HackerRank
  • Equal Sum Partition – HackerRank