[프로그래머스 :: DP] N으로 표현 C++

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

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

 동적계획법으로 문제를 풀기위해 데이터를 어떻게 구성해야하는지 여러 방법을 고민해봐야 한다. 3개 사용했을 때는 2개 사용한 경우와 1개 사용한 경우를 합친 경우다!라는 발견을 할 수 있어야 동적계획법으로 문제를 풀 수 있다.

 증말 쉽지 않다~

 

 N을 1개 사용했을 때, 2개 사용했을 때, 3개 사용했을 때, K개 사용했을 때로 나누어서 생각하는 것이 실마리. K개 사용하여 나온 숫자의 그룹을 S(K)라고 하자. S(2)는 S(1)과 S(1)을 사칙연산 한 경우를 넣고 N을 겹쳐만든 NN을 추가하면 된다.

S(1) = { 4 }   S(2) = { 44 } + { 4+4, 4-4, 4*4, 4/4 }  <-  S(1)과 S(1)을 사칙연산 한 그룹

 

다음 S(2)는 겹쳐만든 44를 추가하고, S(1)과 S(1)을 사칙연산 한 결과를 추가한다. S(2)는 2개를 사용한 집합이고 S(1)은 1개를 사용한 집합이다. S(3)는 겹쳐만든 444를 추가하고 S(1)과 S(2)를 사칙연산한 결과와 S(2)와 S(1)을 사칙연산한 결과를 추가한다. 

 

 4를 2개 사용한 S(2) = { 44, 4+4, 4-4, 4*4, 4/4 }에 S(1) ={ 4 }를 어떤 방식으로 연산해도 3개를 사용하게 되는 것이다.

그래서 S(3) = S(1) 과 S(2)의 연산결과를 활용할 수 있다. S(1)과 S(1)의 연산결과는 2개를 사용하였으므로 S(3)에 넣어주면 안된다.

#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <iostream>

using namespace std;
int duplicating_N(int N,int idx){
    int duplicated_N = 0;
    while(idx>0){
        duplicated_N += pow(10,idx-1)*N;
        idx--;
    }
    return duplicated_N;
}

int solution(int N, int number) {
    if(N==number) return 1; // 테스트 케이스 9를 통과하기 위한 예외처리. (N=5, number=5, 정답1)
    int idx = 1;
    vector<set<int>> set_V(9,set<int>()); // 8개까지 사용, 0을 빼고 쓴다.
    set_V[1].insert(N);
    int duplicated_N = N;
    for(int k=2; k<=8; ++k){
        for(int i=1; i<k; ++i){
            int j=k-i;
            for(int a:set_V[i]){
                for(int b:set_V[j]){
                    if(a-b>0) set_V[k].insert(a-b);
                    if(b!=0) set_V[k].insert(a/b);
                    set_V[k].insert(a+b);
                    set_V[k].insert(a*b);
                }
            }
        }
        set_V[k].insert(duplicating_N(N,++idx)); //중복되는 N값을 추가
        if(set_V[k].find(number)!=set_V[k].end()) return k;
    }
    return -1;
}

 이 풀이방법을 보면서 STL의 set을 알게 되었다. set은 값이 중복되어 저장되지 않는다. set을 활용하면 중복된 결과 값으로 인해 늘어나는 데이터 개수를 줄일 수 있다.

 또 set은 값이 정렬되어 저장되기 때문에 unordered_set을 사용하면 더 빠른 성능을 기대할 수 있다.

 

도움 많이 받은곳, 댓글을 보고 이해가 됬다. gurumee92.tistory.com/164

프로그래머스 문제 풀이 N으로 표현

 

 

 2시간 넘게 내 나름의 로직을 찾고 구현했다. 나름 적절한 규칙을 찾았다고 생각했는데, 생각뿐이었다.

 예제 하나를 만들어 직접 돌려보면서 규칙을 찾았다. 아니 규칙을 내 맘대로 만들었다? 될줄알고 설랬다.

 

 어떻게 문제를 풀지 로직을 생각해내면 바로 코드를 짜지 않고 문제풀이를 찾아보는 편이다. 내 로직에 맞는 문제풀이가 있다면 자신감을 가지고 코드를 짜는데, 내 로직이 없다면, 내가 새로 발견했나? 싶어서 열심히 짜본다. 그리고 시간을 날린다. 

 

 내가 생각한 로직이 다른 사람 코드에 보이지 않을 때 이 로직으로 문제가 풀리면 정말 기분이 좋다. 하지만 이렇게 삽질한 걸로 끝이날 때도 있다. 내 로직이 맞는지 틀렸는지 확신이 서지 않은 상태에서 코드를 직접 구현해서 확인해봐야 하는가? 시간을 아끼고 다른 사람의 좋은 로직을 따라가기만 해도 훌륭한것 아닌가? 생각해보면 앞으로도 계속 이렇게 시간을 날려야겠다는 생각이 든다. 틀릴 수도 있따! 시간만 대가로 지불하면 된다. 내가 생각하는 바를 구현하고 테스트하는 이가 프로그래머가 아닐까? 다른 사람이 적어놓은 코드를 어물쩡 외워서 문제를 풀면 재미없을 것 같다.

 

주의 틀린풀이, 삽질한 풀이

1. number가 N, NN, NNN, NNNN ..... 중 무엇과 더 가까운지 찾는다.
2. 1에서 구한 값에서 +- N, 2N, 3N .... 중 무엇과 더 가까운지 찾는다.
3. 2에서 구한 값에서 N미만의 값을 더해준다.

이렇게 구현해서 바로 틀려버렸다. NN/N 은 항상 11로 우선순위가 높은 최적해가 나온다. 이 경우를 더 업데이트해주어야 한다. 추가적으로 NNN/NN과 NNNN/NN을 추가해서 또 비교해보아야한다. 백터에 값을 넣고 최적값을 찾아나가면 될꺼 같기도? 그치만 그런식으로 코드를 짜지 않아서 갈아엎어야한다. 다시 짠다면 얼마나 길어질지, 어떤 예외처리를 염두해야할지 사실 엄두가 안났다. 이 시점에서 이 코드로 문제를 푸는 것이 힘들겠다고 판단했다.

 

Case1

     - N이 정해지면 0부터 N-1까지 최적해는 정해져있다.

Case2

     - N 배수값이 가지는 최적해는 N으로 나눈 나머지이다.

     - N 배수값에서 그 다음 배수 값 전 수들의 최적값을 구하려면 

       +-배수 + Case1을 반환하면 된다.

 

Case3

     - NN, NNN, NNNN, NNNNN은 Case2보다 우선 순위가 높은 최적값이다. number가

       N~,NN 사이에 있는지아니면 NN~NNN사이에 있는지 찾는다.

     - NN과 NNN의 중간값을 기준으로 NN에서부터 시작할지 NNN에서부터 시작할지 정한다. 

     - Case2를 적용해서 풀이한다.

       NN에서 시작했다면 N을 점점 더해주면서 카운트를 늘리고.

       NNN에서 시작했다면 N을 점점 빼주면서 카운트를 늘린다.

     - 추측한 이때 N만큼 더하거나 빼주었으므로 추측한 값과 number의 차이는 N보다 작은 값이다.

       Case1을 활용하여 카운트를 늘려준다.

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

// 숫자 N, NN, NNN, NNNN을 만들어주는 Utility
int duplicatedNumber(int N, int i){
    int dup = 0;
    while(i>=0){
        dup += N * pow(10,i-1);
        i--;
    }
    return dup;
}

int solution(int N, int number) {
    vector<int> v(N,0);
    // 0과 1은 항상 고정되어 있다.
    v[0]=2; v[1]=2; v[N]=1;
    // 1에서 멀어질수록 1을 더해준다. 1을 더할때 N/N이 사용된다.2~(N-1)까지 채운다.
    for(int i=2; i<N; ++i){ v[i]= i*2; }
    // N에서 멀어질수록 1을 빼주는 방법이 더 효과적이면? 업데이트
    for(int i=N-1; i>=2; --i)
        if(v[i] > v[N]+(N-i)*2 ) v[i] = v[N]+(N-i)*2;
        
   int i=0;
   int Approxi = -1;
   //N, NN, NNN....중 number를 넘지않는 NN..을 찾는다.
   while(duplicatedNumber(N,i)<= number){ i++; }
    Approxi = duplicatedNumber(N,--i);
    int min = duplicatedNumber(1,i);
    int max = duplicatedNumber(1,i+1);
    
    // number는 (NN...) ~ (NNN...)사이에 위치한다.
    // 이 때 중앙값을 기준으로 NN..에서 계산을 시작할지, NNN..에서 계산을 시작할지 나눈다.
    int middle = ( min+max ) / 2;
    int j=0;
    int start = min*N;
    // NN..에서 시작
    if( N*middle > number ){
        start = min*N;
        // 가장 가까운 배수를 찾는다.
        while(start<number){
            start += N;
            j++;
        } start-=N; j--; // 원하는 값은 직전의 값이다.
    // NNN...에서 시작
    } else if( N*middle < number ){
        start = max*N; 
        //i값은 min 값을 기준으로 설정되므로, max값을 사용하면 더해줘야 한다.
        i++;
        // 가장 가까운 배수를 찾는다.
        while(number<start){
            start -=N;
            j++;
        }
    } else { return middle; } // 딱 맞아 떨어지는 배수이므로 바로 답을 전달한다.
    
    int gap = number-start;
    if(gap==0) return i+j; // 
    if(gap>=N){ "Error Out of Bound\n"; }
    return i+j+v[gap];
}