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

풀이

dp를 이용해 풀었다.  임의의 숫자 i에 대해서 N으로만 표현하는 최소 횟수를 구해야하는 문제이다.

사칙연산을 할 수 있기때문에 i에 대해 +,-,*,/를 해주어서 최소횟수를 갱신시켜주었다.

dp 배열의 초기화는 N이 1일때는 최소 N번으로 표현할 수 있고 (1+1+1...)
N이 1보다 클 때는 N*2번으로 표현할 수 있다. (2/2 + 2/2 + .. ) 

또한 N으로만 이루어져있는 숫자들은 따로 초기화를 해주었다. N=5, dp[5]=1 ,dp[55]=2 , dp[555] =3

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> dp;
int solution(int N, int number) {
    int answer = 0;
    dp.resize(32001);
    for(int i=1;i<32001;i++){
        if(N==1)
            dp[i]=i;
        else
            dp[i]=2*i;
    }
    
    int j=1;
    int index=N;
    while(index<32001){
        dp[index] = j;
        index= index * 10 +N;
        j++;
       
    }
    
    for(int i=1;i<=32001/2;i++){
        //곱하기
        for(int j=1;j<=i;j++){
            if(i%j==0){
               int k = i/j; 
                dp[i]=min(dp[i],dp[j]+dp[k]);
            }
            
        }
        //나누기
        for(int j=1;i*j<=32001/2;j++){
            dp[i] = min(dp[i],dp[i*j]+dp[j]);
        } 
        
        
        //더하기
        for(int j=1;j<=i;j++){
            dp[i] = min(dp[i],dp[i-j]+dp[j]);
        }   
           
        //빼기
        for(int j=1;j<=i;j++){
            dp[i] = min(dp[i],dp[i+j]+dp[j]);
        }
       
        
    }
  
    
    if(dp[number]>8)
        answer=-1;
    else
        answer= dp[number];
   
    return answer;
}