프로그래머스 : N으로 표현 c++

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

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

 

DP는 진짜 너무 어렵다

 

풀이

1. 연산 방식으로 인한 count이기 때문에, 배열을 사용한 DP가 아닌, 함수내에서 answer를 업데이트 하는 방식을 사용

 

2. 연산 결과가 정답과 일치하면, 숫자를 사용한 횟수를 answer와 비교

 

3.  for문을 사용하는 이유는

ex) 55를 쓴다고 그러면 숫자 2개를 쓰는거니까, cnt에 이 자릿수만큼 더해줘야 한다.

 

 

#include <string>
#include <vector>
#include <limits>

using namespace std;

int answer = numeric_limits<int>::max();

void dp(int goal,int cnt,int now,int N)
{
    int value = 0;
    
    if(cnt >8)
        return;
    if(now == goal)
    {
        answer = min(answer,cnt);
        return;
    }
    
    for(int i=0;i<8;i++)
    {
        value = N + 10*value;
        dp(goal, cnt+i+1,now+value,N);
        dp(goal, cnt+i+1,now-value,N);
        dp(goal, cnt+i+1,now*value,N);
        dp(goal, cnt+i+1,now/value,N);
    }
    
}

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