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

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42895#

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(int N, int number) {
    vector<set<int>> dp(9);
    
    int base = 0;
    for (int i = 1; i <= 8; i++) {
        base = base * 10 + N;
        dp[i].insert(base);
    }
    
    for (int i = 1; i <= 8; i++) {
        for (int j = 1; j < i; j++) {
            for (int x : dp[j]) {
                for (int y : dp[i - j]) {
                    dp[i].insert(x + y);
                    dp[i].insert(x - y);
                    dp[i].insert(x * y);
                        
                    if (y != 0) {
                        dp[i].insert(x / y);
                    }
                }
            }
        }
        
        if (dp[i].count(number)) {
            return i;
        }
    }

    return -1;
}

---

📝 풀이

N을 i번 사용해서 만들 수 있는 숫자들을 저장 할 컨테이너(dp)를 선언합니다.

우선 N을 최대자리까지 사용하여 dp에 저장합니다.

예를 들어 N = 5라면 5, 55, 555, 5555 등을 저장합니다.

 

i는 N을 사용한 횟수이고 j와 i-j로 나누어 각각을 조합하여 새로운 숫자를 만듭니다.

예를 들어 i = 2 , j = 1, i-j = 1인 경우 x와 y는 dp[1]이 되어 사칙 연산 값들이 dp[2]에 저장됩니다.

• 5 + 5 = 10
• 5 - 5 = 0
• 5 * 5 = 25
• 5 / 5 = 1

dp[i]에 number가 있다면 사용한 횟수 i를 return 합니다.

8번 이하로 만들 수 없다면 -1을 return 합니다.