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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

동적계획법으로 분류되어있지만 당장 생각나지 않고 N의 값이 작아서 완전 탐색으로 해결하였다.

풀이

DFS를 통해 N ~ NNNNNNNN 까지 생성하여 사칙연산을 반복하여 number가 될 떄까지 탐색한다.

코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int num, ans = 9;

void dfs(int N, int cnt, int cur){
    if(cnt >= 9) return;
    if(num == cur){
        ans = min(ans, cnt);
        return;
    }
    int tmp = 0;
    for(int i=0; i+cnt<9; i++){
        tmp = 10 * tmp + N;
        dfs(N, i+cnt+1, cur + tmp);
        dfs(N, i+cnt+1, cur - tmp);
        dfs(N, i+cnt+1, cur * tmp);
        dfs(N, i+cnt+1, cur / tmp);
    }
}

int solution(int N, int number) {
    num = number;
    dfs(N, 0, 0);
    ans = ans == 9 ? -1 : ans;
    return ans;
}