개요

프로그래머스: 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 합니다.

접근 방식

1. 문제를 보자마자 예전에 푼 문제가 떠올랐다.
   백준 : 모노디지털표현 문제와 똑같다.
   하지만, 그때 확실히 내것으로 만드는데 실패했는 지 다시 푸는데 문제풀이의 핵심을 떠올리지 못했다.

2. 기본적인 틀은 숫자는 총 8개이다.
   8개까지 만들 수 있는 모든 경우의 수를 다 set에 저장을 한 후, 마지막에 set을 순회하며 답이 있는지 체크한다.

3. set의 배열을 크기9로 할당을 해주고 선언해준다.

   set<int> allNums[9];

4. makeSet함수를 통해 set을 완성시켜준다.

   각 makeSet함수에 인자로 몇개의 n을 사용해 set에 넣을 건지 정하는 nAmount값을 넣어준다.

   void MakeSet(int nAmount,int calNum){

   calNum은 solution함수에서 받은 N값이다

   i번째 set에는 i개의 N을 이어붙인 숫자를 저장해준다.
   예를 들어 N이 5, nAmount가 3이면 5 세개를 이어붙여 만들 수 있는 555와 -555가 저장된다.

     int tmp=0;
     for(int i=0;i<nAmount;i++){
         tmp = tmp*10+calNum;
     }
     
     allNums[nAmount].insert(tmp);
     allNums[nAmount].insert(-tmp);
     

   그 후, i번째 set과 nAmount-i번째 set의 모든 수들을 다 연산 후, 연산값을 set에 넣어준다.

   for(int i=1;i< nAmount;i++){
         //kAmount개의 숫자가 필요하므로 i번째 set과 kAmount-1번째 set을 조합해야함
         for(int A : allNums[i]){
             for(int B : allNums[nAmount-i]){
                 if(i<=nAmount/2){
                 allNums[nAmount].insert(A+B);
                 allNums[nAmount].insert(A-B);
                 allNums[nAmount].insert(A*B);
                 }
                 if(B) allNums[nAmount].insert(A/B);
             }
         }
     }

   왜 i번째와 nAmount-i번째를 연산하냐하면 숫자의 갯수를 nAmount개로 맞춰야하기 때문이다.
   무조건 N을 nAmount개를 써서 우리가 원하는 number을 맞춰야하므로
   i번째 set과 nAmount-i번째 set을 연산해야한다.

   i, nAmount-i를 서로 연산하는 특성상 i와 nAmount-i가 진행하다가 서로 교차되는 부분부터
   연산값들이 중복된다. 따라서 nAmount/2값까지만 i를 조사해도 무방하다.
   ex) (1, 4), (2, 3), (3, 2), (4, 1) 이런식이면 (1, 4), (4, 1 )와 (2,3) (3,2)값이 중복이된다.

   주의점은 B가 0값이 될수도 있어서 B인지 체크해야한다.
   

전체 코드

#include <string>
#include <vector>
#include <set>

using namespace std;
set<int> allNums[9];

void MakeSet(int nAmount,int calNum){
   int tmp=0;
   for(int i=0;i<nAmount;i++){
       tmp = tmp*10+calNum;
   }
   
   allNums[nAmount].insert(tmp);
   allNums[nAmount].insert(-tmp);
   
   for(int i=1;i< nAmount;i++){
       //kAmount개의 숫자가 필요하므로 i번째 set과 kAmount-1번째 set을 조합해야함
       for(int A : allNums[i]){
           for(int B : allNums[nAmount-i]){
               if(i<=nAmount/2){
               allNums[nAmount].insert(A+B);
               allNums[nAmount].insert(A-B);
               allNums[nAmount].insert(A*B);
               }
               if(B) allNums[nAmount].insert(A/B);
           }
       }
   }

}

int solution(int N, int number) {
   for(int i=1;i<=8;i++){
       MakeSet(i,N);
   }
   int i=1;
   for(i;i<9 && allNums[i].find(number) == allNums[i].end();i++){ }
   if(i>8)
       return -1;
   else 
       return i;
}

문풀후생

두번째 고민하고 풀어보니 이젠 확실히 방법을 안 것 같다.
기본적인 개념은 숫자 1개부터 N개를 써서 만든 모든 경우의 수를 미리 set에 저장한 후, 해당 set에서 탐색하는 개념이다.
왜 1개부터 N개를 미리 만들어놓냐? 하면 2개를 이용해 만든 값과 3개를 이용해 만든 값들이 다 다를 수 있다.
1~N개의 숫자로 만들수 있는 모든 경우의 숫자들을 다 넣고 해당 숫자들을 다 연산하며 다시 set에 넣는 과정을 통해 N개의 숫자를 이용한 모든 경우의 수를 탐색할 수 있다.

마지막 solution함수 부분에 저런식으로 반복문을 쓰는 부분도 오랜만에 보니 신선했다..
예전에 푼 문제들 조금씩 다시 봐야할것같다.