[프로그래머스] N으로 표현 풀이 (DP)

문제 소개

오늘 풀었던 프로그래머스 - N으로 표현 문제를 정리합니다.

이 문제는 숫자 N을 사칙연산과 이어붙이기만으로 target number를 만드는 문제입니다.

문제의 핵심은 "N을 최대 8번까지 사용해서 최소한의 사용으로 target을 만들 수 있는지"를 찾는 데 있습니다.

문제 링크: N으로 표현 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. DP(동적 프로그래밍) 을 이용해 점진적으로 가능한 숫자들을 만들었습니다. 
   • dp[i] : 숫자i번 쓰고 만들 수 있는 수 모음
2. 이어붙이는 숫자(예: 5, 55, 555)도 고려해야 했습니다.
3. 사칙연산(+, -, *, /)을 통해 조합할 수 있는 모든 경우를 생성했습니다.
4. 숫자 사용 횟수를 1개부터 8개까지 늘려가면서 원하는 수가 만들어지는지 확인했습니다.

 

---

해결 과정 및 코드

핵심 아이디어

1. dp[i] = N을 i번 사용해서 만들 수 있는 모든 수들의 집합으로 정의합니다.
2. dp[1] = {N}, dp[2] = {NN, N+N, N-N, N*N, N/N} 이런 식으로 채워갑니다.
3. 수식을 만들 때, (앞에 만든 숫자 집합) + (뒤에 만든 숫자 집합) 조합도 모두 고려합니다.
4. N을 이어붙인 수 (5, 55, 555 같은 것)도 추가해줘야 합니다.
5. N을 8번까지 사용했는데도 원하는 수를 만들지 못하면 -1을 반환합니다.

코드

시간 복잡도 : 최악의 경우 O(8^2 * M^2)에 가까울 수 있습니다. (M = 각 단계에서 만들 수 있는 숫자의 개수)

import java.util.*;

public class Solution {
    public int solution(int N, int number) {
        if (N == number) return 1;
        
        List<Set<Integer>> dp = new ArrayList<>();
        // 8번 사용하는 경우만 저장할거임
        for (int i = 0; i <= 8; i++) {
            dp.add(new HashSet<>());
        }
        
        dp.get(1).add(N);
        
        for (int i = 2; i <= 8; i++) {
            Set<Integer> current = dp.get(i);
            
            // 이어붙이기: 예를 들면 5, 55, 555
            int concatNumber = Integer.parseInt(String.valueOf(N).repeat(i));
            current.add(concatNumber);
            
            // 이전에 만든 경우를 합친 경우 고려
            for (int j = 1; j < i; j++) { // dp[3] = (dp[1]과 dp[2] 조합, dp[2]와 dp[1] 조합)
                Set<Integer> set1 = dp.get(j);
                Set<Integer> set2 = dp.get(i - j);
                
                for (int a : set1) {
                    for (int b : set2) {
                        current.add(a + b);
                        current.add(a - b);
                        current.add(a * b);
                        if (b != 0) current.add(a / b);
                    }
                }
            }
            
            if (current.contains(number)) {
                return i;
            }
        }
        
        return -1;
    }
}

 

---

추가: 값 복사 vs 참조 복사 (중요 개념)

이 문제를 풀 때, Set<Integer> current = dp.get(i); 와 같은 코드가 나옵니다.
이 부분에서 "값 복사인가? 참조 복사인가?" 헷갈릴 수 있는데, 정리하면 다음과 같습니다.

복사 방법설명특징

Set<Integer> current = dp.get(i);	참조 복사	current와 dp.get(i) 둘 다 같은 객체를 가리킴
new HashSet<>(dp.get(i))	값 복사	완전히 독립적인 새 Set 생성
Set<Integer> copy = (Set<Integer>) ((HashSet<Integer>) original).clone();	값 복사	clone은 별도 객체를 리턴, 형변환 필요

• current.add(x)를 하면 **dp.get(i)**에도 영향이 가는 이유는 참조 복사이기 때문입니다.
• 복사본을 따로 만들고 싶으면 new HashSet<>(원본)이나 clone()을 사용해야 합니다.

보통은 new HashSet<>(원본) 방식을 더 선호합니다. (형변환이 필요 없고 가독성이 좋기 때문)