본문 바로가기
Programming Solve/프로그래머스

프로그래머스 - N으로 표현 / C++

by msm1029 2022. 3. 2.
반응형

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42895

 

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

 

programmers.co.kr

 

 

문제 풀이

N으로 표현할 수 있는 경우는 N 한 가지이다. 이를 DP[0]이라고 하면 DP[0] = { N }이다.

 

N 2개로 표현할 수 있는 경우는 NN, (N+N, N-N, N*N, N/N) 이며 이를 DP[1]이라 하면
DP[1] = { NN, N+N, N-N, N*N, N/N } 이다.

 

N 3개로 표현할 수 있는 경우는 NNN, (NN+N, NN-N, NN*N, NN/N), {(N+N)+N), (N+N)-N, (N+N)*N, (N+N)/N}, ... 이다. 이를 DP[2]라 하면 DP[2]는 DP[1]와 DP[0]의 사칙연산, 그리고 DP[0]와 DP[1]의 사칙연산들로 이루어져있음을 알 수 있다.

 

반복하여 규칙을 찾아보면 DP[3]은 DP[2]와 DP[0]의 사칙연산, DP[1]과 DP[1]의 사칙연산 DP[0]과 DP[2]의 사칙연산으로 이루어져있음을 알 수 있고 DP[k] = DP[i] +-*/ DP[j]이며 k = i + j + 1이라는 점화식을 세울 수 있다.

 

따라서 0은 N 한 가지임이 명백하므로 1부터 8까지 반복문을 돌며 앞선 점화식대로 연산을 수행하여 set에 넣는다. set을 쓰는 이유는 연산과정에서 중복값이 발생하기 때문이다.

 

모든 경우의 수를 생성하였으면 set을 순차적으로 돌며 number를 찾는다. 만약 i번째 set에서 찾았다면 i+1개를 사용하여 number를 만드는 것이 최소 사용 횟수이다.

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int solution(int N, int number) {
    int answer = -1;
    unordered_set<int> s[8];
    
    int sum = 0;
    for(int i=0; i<8; i++){
        sum = sum*10 + N;
        s[i].insert(sum);
    } //N, NN, NNN... 삽입
    
    for(int k=1; k<8; k++){
        for(int i=0; i<k; i++){
            for(int j=0; j<k; j++){
                if(i+j+1 != k) continue;
                for(int a : s[i]){
                    for(int b : s[j]){
                        s[k].insert(a+b);
                        if(a - b > 0) s[k].insert(a-b);
                        s[k].insert(a*b);
                        if(a / b > 0) s[k].insert(a/b);
                    }
                }
            }
        }
    }
    
    for(int i=0; i<8; i++){
        if(s[i].find(number) != s[i].end()){
            answer = i + 1;
            break;
        }  
    }
    
    return answer;
}

 

코드 리팩토링

#include <bits/stdc++.h>
using namespace std;

int solution(int N, int number) {
    int answer = -1;
    unordered_set<int> s[8];
    
    int sum = 0;
    for(int i=0; i<8; i++){
        sum = sum*10 + N;
        if(sum == number) return i+1;
        s[i].insert(sum);
    }
    
    for(int k=1; k<8; k++){
        for(int i=0; i<k; i++){
            for(int j=0; j<k; j++){
                if(i+j+1 != k) continue;
                for(int a : s[i]){
                    for(int b : s[j]){
                        if(a+b == number) return k+1;
                        s[k].insert(a+b);
                        
                        if(a - b > 0){
                            if(a-b == number) return k+1;
                            s[k].insert(a-b);
                        }
                        
                        if(a*b == number) return k+1;
                        s[k].insert(a*b);
                        
                        if(a / b > 0){
                            if(a / b == number) return k+1;
                            s[k].insert(a/b);
                        }
                    }
                }
            }
        }
    }
    
    return answer;
}

set에 삽입하기 전, number를 찾으면 바로 return 해준다.

반응형