<Programmers> Dynamic Programming_N으로 표현 c++

문제는 N과 number가 주어질 때 N과 사칙 연산만 사용해서 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 구하는 문제이다.

e.g. N=5, number=12인 경우
12=5+5+(5/5)+(5/5) ->6개
12=55/5+5/5 ->5개
12=(55+5)/5 ->4개
이 중 최솟값은 4이므로 4를 return

여기서 역으로 생각해서 N이 1개, 2개, 3개... 일 때 만들 수 있는 수의 집합을 생각해본다. 이 집합 중에 찾는 number이 있으면 몇 개로 만들 수 있었는지 return한다.

5가 1개일 때 = {5}
5가 2개일 때 = {55, 5+5, 5-5, 5*5, 5/5}
5가 3개일 때 = {555, 5+55, 55+5, 5+5+5, 5-55, 55-5, 5-5-5, 5*55, 55*5, 5*5*5, 5/55, 55/5 , 5/5/5}

여기서 보면 2개일 때 사용했던 연산이 3개일 때 사용했던 연산에 쓰이는 것을 볼 수 있다. 예를들어 5가 3개일 때 {5+5+5}는 5가 1개일 때 {5}와 5가 2개일 때 {5+5} 연산을 더한 것이다.

1. Memoization 방식을 떠올릴 수 있고 이것을 dp로 나타내보자

vector<unordered_set<int>> dp(8);
(이차원 벡터를 선언하는 대신 unordered_set을 사용한 이유는 안에 저장되는 값은 정렬될 필요가 없고, 중복된 값은 두 번 이상 쓸 필요가 없기 때문에)

e.g. N=5, number=12인 경우
(여기서 &은 모든 사칙 연산을 의미)

dp[0]=5가 1개인 경우 {5} ---N0
dp[1]=5가 2개인 경우 {55, N0 & N0} ---N1
dp[2]=5가 3개인 경우 {555, N0 & N1, N1 & N0} ---N2
dp[k]=5가 k개인 경우 {555... (k개 만큼), Ni & Nj (i+j+1=k 인 집합)}

2. k개의 N을 만드는 함수

5, 55, 555와 같은 숫자를 만드는 함수

#include <cmath>

int makeNumber (int N, int idx) {
    int answer=0;
    while (idx>0) {
        idx--;
        answer+=N*pow(10, idx);
    }
    return answer;
}

3. dp[k]에 값을 저장

(1) dp[0]은 1개의 N으로 number을 만드는 경우 이므로 1
(2) 처음 모든 경우에는 5, 55, 555, 5555와 같은 숫자가 기본으로 들어가기 때문에 2번에서 만든 k개의 N을 만드는 함수를 호출해서 저장
(3) i+j+1=k 인 경우의 수만 뽑아서 사칙 연산한 값을 dp[k]에 저장 (이때, 뺄셈과 나눗셈 주의)
(4) dp[k].count(number)>0, 즉 k+1개의 N으로 만들 수 있는 집합의 원소 중 number의 갯수가 0이상, 즉 있다면 k+1을 return

  for (int k=1; k<MAX; k++) {
      dp[k].insert(makeNumber(N, k+1));
 
      for (int i=0; i<MAX; i++) {
          for (int j=0; j<MAX; j++) {
              if (i+j+1!=k) continue;
         
              for (int op1: dp[i]) {
                  for (int op2: dp[j]) {
                      dp[k].insert(op1+op2);
                      if (op1-op2>0) dp[k].insert(op1-op2);
                      dp[k].insert(op1*op2);
                      if (op1/op2>0) dp[k].insert(op1/op2);
                  }
              }
          }
      }
        if (dp[k].count(number)>0) 
            return k+1;
  }

전체코드

#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>

const int MAX=8;

using namespace std;

int makeNumber (int N, int idx) {
  int answer=0;
  while (idx>0) {
      idx--;
      answer+=N*pow(10, idx);
  }
  return answer;
}

int solution(int N, int number) {
  if (N==number) return 1; // 이 경우의 수도 꼭 포함해주어야 함
  vector<unordered_set<int>> dp(MAX);
 
  dp[0].insert(N);
 
  for (int k=1; k<MAX; k++) {
      dp[k].insert(makeNumber(N, k+1));
     
      for (int i=0; i<MAX; i++) {
          for (int j=0; j<MAX; j++) {
              if (i+j+1!=k) continue;
             
              for (int op1: dp[i]) {
                  for (int op2: dp[j]) {
                      dp[k].insert(op1+op2);
                      if (op1-op2>0) dp[k].insert(op1-op2);
                      dp[k].insert(op1*op2);
                      if (op1/op2>0) dp[k].insert(op1/op2);
                  }
              }
          }
      }
        if (dp[k].count(number)>0) 
            return k+1;
  }
  return -1;    
}