[프로그래머스 Lv.3 / C++] Day85. N으로 표현

2024. 08. 27 - 코딩테스트 스터디 Day85

 
 

01. 문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
5를 사용한 횟수는 각각 6,5,4입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용 횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 
 

02. 제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

 
 

03. 입출력 예

N	number	return
5	12	4
2	11	3

 
 
입출력 예 설명
 
예제 #1
문제에 나온 예와 같습니다.
 
예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

4. 풀이 및 답 

N을 n개 사용햇 수를 만드는 경우를 dp[n]이라고 하면
dp[1] = { 5 }
dp[2] = { 55, 5 + 5, 5 - 5, 5 * 5, 5 / 5 }
dp[3] = { 555, 55 + 5, 5 + 55, 5 + 5 + 5, ... } 등이 된다
 
이를 통해 알 수 있는 것은 dp[i] = dp[i - 1] + do[i - j - 1] (0 <= j < i) 라는 것이다
 

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

using namespace std;

int solution(int N, int number) {
    int answer = -1;
    set<int> dp[8];
    
    int num = 0;
    for (int i = 0; i < 8; i++) {
        num = 10 * num + N;
        dp[i].insert(num);
    }
    
    for (int i = 1; i < 8; i++) {
        for (int j = 0; j < i; j++) {
            for (int a : dp[j]) {
                for (int b : dp[i - j - 1]) {
                    dp[i].insert(a + b);
                    dp[i].insert(a - b);
                    dp[i].insert(a * b);
                    if (b != 0) {
                        dp[i].insert(a / b);
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < 8; i++) {
        if (dp[i].count(number)) {
            answer = i + 1;
            break;
        }
    }
    
    return answer;
}

위에서 알아낸 점화식에 기반하여 코드를 작성했다.
 
N을 나열해서 수를 표현한 경우와, N을 사칙연산하여 수를 표현한 경우를 나눠 계산한 뒤 dp에 저장했다.
set은 중복을 제거한다는 성질이 있는 자료구조이기 때문에 효율적이다
 
 

정답!

---

 
 
참고한 게시글

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