[프로그래머스 Lv3] : N으로 표현

문제 링크

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

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

숫자 N으로 특정한 수 number을 만드는데 필요한 N의 최소 개수 리턴

 

풀이

먼저 주어진 예제를 보자.

5를 이용해서 12를 만드는 방법에는 3가지가 있다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

 

첫번째, 두번째, 세번째 방법은 각각 5를 6번, 5번, 4번 이용해서 만들었다.

우리가 5를 이용해서 숫자를 만드는 방법은 5가지가 있다.

1. 5를 이어붙인다. ex) 55, 555, 5555, ...

2. +연산 사용. ex) 5 + 5, 55 + 5, ...

3. - 연산 사용. ex) 5 - 5, 55 - 5, ...

4. * 연산 사용. ex) 5 * 5, 55 * 55, ...

5. / 연산 사용. ex) 5 / 5, 55 / 5, ...

 

이렇게 이어붙이기와 4가지의 연산을 이용해서 숫자들을 만들 수 있다.

• 1. 이어붙이기 방식

N을 1개 이어붙이면 N,  N을 2개 이어붙이면 NN,  N을 3개 이어붙이면 NNN...

for(int i = 1; i<=8; i++){
        int num = N;
        for(int j = 1; j<i; j++){
            num = num * 10 + N;
        }
}​

위의 과정을 통해 N을 i번 이어붙인 수를 만들 수 있다.

 

• 2,3,4,5 연산 방식

예를 들어 5를 3번써서 임의의 숫자를 만든다고 할 때,

5를 한 번써서 만든 수와 5를 두 번 써서 만든 수를 4가지 연산(+, -, *, / ) 을 이용해서 5를 세 번 사용한 숫자들을 나타낼 수 있다.

N을 한 번 사용해 만든 수와 두 번 사용해 만든 수를 이용해서 세 번 사용해 만든 수들을 만든다.

=> Bottom - Up 방식

따라서 임의의 K에 대해 N을 K번 사용해 만들 수 있는 숫자들을 알아내기 위해서는 1번 ~ K-1번 사용해 만든 숫자들을 모두 알고 있어야한다. 따라서 DP벡터에 숫자들을 저장해둔다.

이때 DP[ i ] 에 들어있는 숫자들은 N을 i번 사용해서 만든 모든 숫자들을 의미한다. 

DP[i]에 들어있는 값들은 중복이 의미가 없으므로 중복을 제거하기 위해 set을 사용했다.

예를 들어 N을 K번 사용해서 숫자를 만들어 보자.

DP[1]에 있는 숫자 ( +,-,*,/ ) DP[K-1]에 있는 숫자, DP[2]에 있는 숫자 ( +,-,*,/ ) DP[K-2]에 있는 숫자, DP[3]에 있는 숫자 ( +,-,*,/ ) DP[K-3]에 있는 숫자, ... , DP[K-1]에 있는 숫자 ( +,-,*,/ ) DP[1]에 있는 숫자를 한 결과들을 모아놓은 것이 DP[K]가 된다.

이때 DP[1]에 있는 숫자를 DP[K-1]에 있는 숫자와 연산한 결과와, DP[K-1]에 있는 숫자를 DP[1]에 있는 숫자를 연산한 결과는 같지 않냐고 생각할 수도 있지만, 만약 연산 과정에서 연산해야할 숫자의 자리를 바꾼 경우도 모두 생각해주었다면 같다고 봐도 되지만 아니면 두 가지 경우는 다른 경우다.

+, * 의 경우는 상관없지만 /, - 경우에는 a - b, a / b 와 b - a, b / a 는 결과가 다르기 때문이다.

 

코드 작성

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <set>
using namespace std;
set<int> DP[10];
 
void init(int N){
    for(int i = 1; i<=8; i++){
        int num = N;
        for(int j = 1; j<i; j++){
            num = num * 10 + N;
        }
        DP[i].insert(num);
    }
}
 
int solution(int N, int number) {
    int answer = 1;
    if(N == number)
        return answer;
    init(N);
    for(int i = 2; i<=8; i++){
        for(int j = 1; j < i; j++){
            for(auto a : DP[j]){
                for(auto b : DP[i-j]){
                    DP[i].insert(a + b);
                    if(a - b > 0)
                        DP[i].insert(a - b);
                    DP[i].insert(a * b);
                    if(a / b > 0)
                        DP[i].insert(a / b);
                }
            }
        }
        if(DP[i].find(number) != DP[i].end())
            return i;
    }
    return -1;
}