프로그래머스 Level3 N으로 표현

문제 설명
아래와 같이 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 함수를 작성하세요.

제한사항
N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.
입출력 예
N number return
5 12 4
2 11 3
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

출처

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

---

풀이 과정

프로그래머스에서 DP문제라고 나와있어서 처음에 DFS문제 같은데 의아했었다.

그래도 DP로 풀어보려고했는데 잘 안되서 DFS로 그냥 풀었다...

최솟값이 8보다 크면 -1 로 리턴한다. 즉 숫자N은 최대 여덟번 사용 가능하다.

그래서 처음에는 DFS 코드를 이렇게 짰다.

void dfs(int index,int n,int target,int result){

    if(index==8){
        return;
    }
    if(result ==target){
        answer = min(answer,index);
    }
    int newN = result*10+n;
    dfs(index+1,n,target,result+n);
    dfs(index+1,n,target,result-n);
    dfs(index+1,n,target,result*n);
    if(result/n!=0){
        dfs(index+1,n,target,result/n);
    }
    dfs(index+1,n,target,newN);


}

이렇게 짰더니 테캐 4개가 계속 통과가 안됬다. 조금 더 생각해보니깐 5가 들어왔을 때 newN은 55가 되어 result인자값으로 넘어간다. 그리고 재귀를 하면 55+5, 55-5 등등이 인자로 넘어가진다.

이렇게 되면 한 숫자만 사용하는 것이 아니기 때문에 문제 조건에 부합하지 않는다.

그래서 dfs 부분을 수정했다

void dfs(int index,int n,int target,int result){

    if(index>8){
        return;
    }
    if(result ==target){
        answer = min(answer,index);
    }
    int newN = 0;
    for(int i=0;i<8;i++){
        newN = newN*10+n;
        dfs(index+i+1,n,target,result+newN);
        dfs(index+i+1,n,target,result-newN);
        if(result!=0){
            dfs(index+i+1,n,target,result*newN);
            dfs(index+i+1,n,target,result/newN);
        }
    }
}

이렇게 하면 애초에 55, 555, 5555... 만 인자로 넘어가기 때문에 잘 통과가 된다.

나누기나 곱하기 하는 부분은 0일 때는 판단할 필요가 없으므로 그 경우는 제외해주면 된다.

DP로 푸는 방법은 다음에 더 찾아봐야겠다...

---

소스 코드

#include <string>
#include <iostream>
#include <vector>

using namespace std;
int answer = 9;
void dfs(int index,int n,int target,int result){

    if(index>8){
        return;
    }
    if(result ==target){
        answer = min(answer,index);
    }
    int newN = 0;
    for(int i=0;i<8;i++){
        newN = newN*10+n;
        dfs(index+i+1,n,target,result+newN);
        dfs(index+i+1,n,target,result-newN);
        if(result!=0){
            dfs(index+i+1,n,target,result*newN);
            dfs(index+i+1,n,target,result/newN);
        }
    }


}

int solution(int N, int number) {
    dfs(0,N,number,0);
    cout<<answer;
    if(answer==9){
        answer = -1;
    }
    return answer;
}