[프로그래머스][C++] N으로 표현

N으로 표현

문제 링크

N으로 표현

분석

주어진 숫자 N을 최대 8번까지 사용하여 사칙연산과 숫자 이어붙이기를 통해 목표 숫자를 만드는 최소 횟수를 구하는 문제입니다.
만약 목표 숫자를 만들 수 없는 경우 -1을 반환합니다.

N을 사용한 횟수에 따라 만들 수 있는 모든 수를 저장하고, 이를 기반으로 더 큰 수를 만들어야합니다.
즉, 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다.

풀이

#include <vector>
#include <unordered_set>

using namespace std;

int solution(int N, int number) {
    int answer = 0;
    
    // N이 처음부터 목표 수와 같다면 1번만에 만들 수 있으므로 바로 반환
    if (N == number)
    {
        return 1;
    }
    
    // dp[i]는 N을 i번 사용해서 만들 수 있는 수들의 집합
    // 1~8까지 사용가능하므로 9개의 공간 확보
    vector<unordered_set<int>> dp(9);
    
    // i는 N을 사용한 횟수 최대 8
    for (int i = 1; i <= 8; ++i)
    {
        int num = 0;
        
        // N을 i번 이어붙인 숫자를 생성해서 dp[i]에 넣는다.
        for (int j = 0; j < i; ++j)
        {
            num = num * 10 + N;
        }
        
        dp[i].insert(num);
        
        // i를 두 부분으로 나누어 이전 결과를 이용하여 새로운 수를 생성
        for (int j = 1; j < i; ++j)
        {
            // dp[j]의 결과와 dp[i - j]의 결과를 조합
            for (int a : dp[j])
            {
                for (int b : dp[i - j])
                {
                    // 사칙연산을 모두 적용하여 dp[i]에 결과 저장
                    dp[i].insert(a + b);
                    dp[i].insert(a - b);
                    dp[i].insert(a * b);
                    
                    // 나눗셈은 0으로 나누는 경우를 제외해야한다.
                    if (b != 0)
                    {
                        dp[i].insert(a / b);
                    }
                }
            }
        }
        
        // 현재까지 만든 수들 중 목표 숫자가 있는 경우 i를 정답으로 반환한다.
        if (dp[i].count(number))
        {
            return i;
        }
    }
    
    // 끝가지 만들지 못했다면 -1을 반환한다.
    return -1;
}

성능 요약

시간 복잡도는 $O(s^2)$입니다.

• 최대 8번 반복하는 반복문 $O(n)$
• 숫자를 이어붙이는 반복문 $O(n)$
• 두 집합의 사칙연산을 진행하는 반복문 $O(s^2)$
• $O(n) + O(n) + O(s^2)$

공간 복잡도는 $O(s)$입니다.

• dp 배열 $O(9) /approx O(1)$
• dp[i]에 저장된 수 $O(s)$

테스트 성능

테스트 1 〉 통과 (0.25ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.11MB)
테스트 3 〉 통과 (0.01ms, 4.15MB)
테스트 4 〉 통과 (3.80ms, 3.63MB)
테스트 5 〉 통과 (3.08ms, 3.95MB)
테스트 6 〉 통과 (0.07ms, 4.13MB)
테스트 7 〉 통과 (0.08ms, 4.2MB)
테스트 8 〉 통과 (4.05ms, 3.82MB)
테스트 9 〉 통과 (0.01ms, 4.02MB)