프로그래머스_N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현 | 프로그래머스

처음 해당 문제를 접했을 때는 DP로 풀려고 하였다.

그런데 DP로 생각해보려니 최적화 원리가 어떻게 적용될 수 있는지 이해가 잘 안되서 쉽지 않았다.

그러던 중 DFS로도 할 수 있지 않을까 생각하였고 다행히 터지지 않고 해결할 수 있었다.

 

DFS로 접근법은 간단하다, 숫자에 대해 연산을 재귀적으로 수행하면서 목적값 number를 찾아가면 된다.

이 때 백트랙킹 조건으로 다음의 두 가지를 포함시켰다.

1) 숫자 사용 수가 8번이 넘어가는 경우

2) 현재까지 만들어둔 결과값 num이 0일 때는 굳이 곱하거나 나누는 경우

 

나누는 것은 당연히 에러 방지용이었고 곱하기는 0에다가 어떤 값을 곱해도 0이기에 숫자를 최대한 적게 사용해야하는 문제의 조건에 어긋나는 행위라고 생각하였다.

#include <string>
#include <vector>
#define MAX 9
using namespace std;
int ans_glb = MAX, num_glb, N_glb; // 전역 변수

void dfs(int cnt, int num){
    // MAX(8)보다 크면 종료
    if(cnt >= MAX)
        return;
    
    // 숫자 값을 찾았으면 작은 값 넣기
    if(num == num_glb)
        ans_glb = min(ans_glb, cnt);
    
    // 숫자 1자리부터 8자리 까지 반복
    int n = 0;
    for(int i=0;i<8;i++){
        n = (n*10) + N_glb; // 1자리부터 8자리까지
        // cnt에 사용 수 만큼 더해주기
        dfs(cnt+i+1, num+n); // +
        dfs(cnt+i+1, num-n); // -
        // 0이 아닐 경우에만
        if(num != 0){
            dfs(cnt+i+1, num*n); // *
            dfs(cnt+i+1, num/n); // /
        }
    }
}

int solution(int N, int number) {
    int answer = 0;
    num_glb = number, N_glb = N; // 지역 변수 -> 전역 변수
    dfs(0,0);
    answer = ((ans_glb==MAX) ? -1 : ans_glb);   // 결과값
    return answer;
}

 

DP로 어떻게 풀 수 있는지 찾아보다가 정리가 잘된 소스코드가 있었다.

https://dev-dream-world.tistory.com/23

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