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

 

코딩테스트 연습 - N으로 표현

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int ans = 9;

void DP(int n, int num, int count, int cur){
    if(count > 8)
        return;
    
    if(cur == num){
        ans = min(ans, count);
        return;
    }
    // 더하기, 붙이기, 나누기
    int temp = 0;
    for(int i = 0; i + count < 9; i++){
        temp = temp * 10 + n;   // n, nn, nnn ...
        DP(n, num, count + 1 + i, cur + temp);
        DP(n, num, count + 1 + i, cur * temp);
        DP(n, num, count + 1 + i, cur / temp);
        DP(n, num, count + 1 + i, cur - temp);
    }
}

int solution(int N, int number) {
    DP(N, number, 0, 0);
    
    if(ans > 8) 
        ans = -1;
    
    return ans;
}

---

 이게 DP인지 DFS인지는 감이 잘 안잡히긴 하지만 경우의수가 많지 않아서 위로도 풀 수 있었습니다. DP 함수에서 중요한건 temp를 통해 새로운 수를 찾아가는겁니다. 기존 수인 cur에 추가적으로 temp를 연산하는 것인데 temp는 10을 곱한 뒤 n 을 더해 n, nn, nnn, nnnn ... 이런 식으로 만들어지게 했습니다.