N으로 표현

 

 

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42895

 

사용 알고리즘: DFS 완전탐색

 

풀이: 재귀함수를 통해 DFS를 구현한다.

사칙연산을 반복하며 재귀함수로 들어가고 이를통해 완전탐색을 구현 한다.

answer(전역) 초기값은 충분히 높게 잡고, N이 사용된 횟수(answer)가 8보다 커지면 -1을 반환한다.

dfs의 parameter는 num, count이고, num은 현재상황 숫자를 나타내고,

count로 몇번 N이 사용되는지를 재귀를 통해 전달한다.

 

#include<iostream>
#include <string>
#include <vector>
using namespace std;
int N, number;
int answer = 1e9;
void dfs(int num, int count) {
    if (count > 8)
        return;
    if (count >= answer)
        return;
    if (num == number) {
        answer = count;
        return;
    }
    
    int tmp = 0;
    for (int i = 0;i < 7;i++) {
        tmp = tmp * 10 + N;
        dfs(tmp + num, count + i + 1);
        dfs(tmp * num, count + i + 1);
        dfs(tmp - num, count + i + 1);
        dfs(num - tmp, count + i + 1);
        dfs(num / tmp, count + i + 1);
        if (num != 0) {
            dfs(tmp / num, count + i + 1);
        }
    }
}
int solution(int N_, int number_) {
    N = N_;
    number = number_;
    dfs(0, 0);
    if (answer > 8)
        return -1;
    else
        return answer;
}
int main() {
    cout << solution(5, 12);
    return 0;
}