프로그래머스: N으로 표현

알고리즘 문제 해결 과정을 기록합니다

September 5, 2025 · 4 min read

#알고리즘 #문제해결 #DP

문제 개요 #

Source: 프로그래머스 문제 링크
Difficulty: Level 3
Key Concept: 동적 계획법

접근 방법 #

동적 계획법은 Top-Down방식과 Bottom-up 방식으로 접근할 수 있다. 먼저 Top-Down방식은 아래 4가지의 구성 요소를 가지고 와야 한다.

초기메롱

dp 초기화
기저 사례(base condition)
메모이제이션(Memoization)
로직(점화식)

장점은 재귀적 형태로 자연스럽게 코드를 작성할 수 있다. 하지만 이후 설명할 반복문을 이용한 Bottom up 방식에 비해 시간이 오래 걸린다. 즉 오버헤드가 추가 발생하며 재귀가 깊어질 수록 오버플로우의 위험이 커진다.

이와 반대로 Bottom up 방식은 반복문을 이용하여 순차적으로 dp배열을 채워나간다. 장점은 빠른 속도와 우수한 메모리 효율성이 있다. 하지만 해당 방식은 직관성이 낮으며 구현이 복잡해질 수도 있다.

따라서 속도와 성능이 우선되는 경우 Bottom up을 사용하고 구조를 잘 이해하고 빠르게 만들어야 하는 경우 Top Down 방식을 사용하면 좋다.

시행착오 #

DP를 처음 해보면서 로직 자체가 생각이 나지 않았다. 다시 DP의 4가지 구성요소를 생각해보면서 dp 배열의 의미를 다시 생각하였다. dp[i]는 숫자 N을 i개 사용하여서 만들 수 있는 수의 집합으로 두었다.

즉 N = 3일 때, dp[2]가 가질 수 있는 수는 $\{3+3, 3*3, 3/3, 3-3, 33\} \rightarrow \{6,9,1,0,33\}$이 된다. 처음에는 dp[i]에 N을 사칙연산 후 N을 하나 더 붙이는 Bottom up 방식을 생각하였다.

dp[1] = {N};
dp[2] = {N+N, N*N, N/N, N-N}

for(int i = 2 ; i <= 9 ; i++){
    for(const int& item: dp[i-1]){
        dp[i].emplace_back(item * N);
        dp[i].emplace_back(item + N);
        dp[i].emplace_back(item - N);
        dp[i].emplace_back(item / N);
    }
    string tmp;
    for(int j = 0 ; j < 2 ; j++){
        tmp += std::to_string(N);
    }
    dp[i].emplace_back(std::stoi(tmp));
}

하지만 해당 방식의 경우 직전의 dp배열에다가 N하나만을 추가하는 방식으로 아래와 같은 예시를 생각하지 못했다. N을 4개를 써서 수를 만들었다고 했을 때는 아래와 같은 경우의 수가 나온다.

N을 1개 사용해서 만든 수 ○ N을 3개 사용해서 만든 수
N을 2개 사용해서 만든 수 ○ N을 2개 사용해서 만든 수
N을 3개 사용해서 만든 수 ○ N을 1개 사용해서 만든 수

(○는 사칙연산 연산자를 의미한다.)

현재의 해결 방식에는 3번의 경우의 수만 고려하고 1번과 2번은 고려하지 않고 있다.

해결 방법 #

#include <bits/stdc++.h>

using std::vector;
using std::string;
using ll = long long;
using std::set;

const int DIGIT_SIZE = 10;
set<ll> dp[DIGIT_SIZE];

int solution(int N, int number) {
    int answer = 9;
    dp[0].insert(0);
    dp[1].insert(N);
    string value = std::to_string(N);
    for(int i = 2 ; i < DIGIT_SIZE ; i++){
        for(int j = 1 ; j < i ; j++){
            for(const auto& fst: dp[j]){
                for(const auto& snd: dp[i-j]){
                    dp[i].insert(fst*snd);
                    dp[i].insert(fst+snd);
                    dp[i].insert(fst-snd);
                    if(snd == 0){ continue; }
                    dp[i].insert(fst/snd);
                }
            }
        }
        value += std::to_string(N);
        dp[i].insert(std::stoll(value));
    }
    for(int i = 1 ; i < DIGIT_SIZE ; i++){
        if(dp[i].count(number)){
            answer = i;
            break;
        }
    }
    return answer > 8 ? -1 : answer;
}

알고리즘 설명 #

먼저 앞서 설명한 모든 경우의 수 즉 4 = 1+3 = 2+2 = 3+1의 경우를 모두 고려하기 위해 다중 반복문을 사용하였다. 문제에서 최소값이 8이 넘는 경우 -1로 리턴하라는 조건이 있었기 때문에 N을 0번부터 8번까지만 있으면 되므로 DIGIT_SIZE = 9가 된다. 9번 반복하면서 N이라는 숫자를 1~8번 사용하여 사칙연산을 할 때 마다 1번 사용한 수와 (i-1)번 사용한 수 … (i-1)번 사용한 수와 1번 사용한 수의 연산을 모두 계산하였다. for(int j = 1; j < i ; j++)반복문을 통해 1~(i-1)번 N으로 수를 만든 배열을 접근, 내부의 enhanced loop를 통해 dp[j]의 원소와 dp[i-j]의 원소에 접근할 수 있었다. 이 때, snd는 0이 될 수도 있고 이는 devide by zero 에러의 원인이 될 수 있으므로 예외 처리를 해 주었다.

마지막으로 N, NN, NNN과 같이 단순히 concatenating하는 경우에는 for(int i)반복문 단에서 하나씩 문자열로 concat 후 stroll을 통해 long long 타입으로 캐스팅하였다.

이제 해당 숫자가 조합에 들어있다면 dp[i].count(number)가 1 이상이 될 것이므로 해당 조건을 통해 최소값을 찾고, answer을 미리 -1로 초기화 시켜 조건문에 걸리지 않는다면 자동으로 -1이 리턴되도록 하였다.

성능 분석 #

Time Complexity: O($4^n$)
Space Complexity: O($4^n$)

실무 활용 #

캐싱 시스템 최적화
가격/할인 최적화 엔진

핵심 정리 #

부분 문제의 분할이 이 문제의 핵심이었습니다.

$$ \text{숫자} N \text{을 }i \text{개 사용해 만든 수} = j \text{개 사용한 숫자 } ○ (i-j) \text{개 사용한 숫자} $$

또한 문제 조건 중 최소값이 8초과라면 -1을 리턴한다라는 조건을 통해 배열의 크기 또한 결정할 수 있었습니다. 자료구조적으로는 중복 값이 필요하지 않았고 빠르게 검색이 되도록 하였어야 했기에 set[^1]을 사용하였고 이를 통해 메모리 효율성도 확보할 수 있었습니다.

참고 자료 #

std::set