[c++] 프로그래머스 :: N으로 표현 (다이나믹 프로그래밍)

 

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

문제 설명

아래와 같이 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 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

나의 답

생각의 흐름

1. 완전 탐색으로 풀 수 있을까?

   주어진 number보다 N이 작을 때는 +, x 연산자를 사용하거나 11배하고

   같을 때는 return하고

   N이 더 클 때는 -, / 연산자를 사용하면 되지 않을까?

   => 시간 복잡도도 클 뿐더러 괄호가 순차적으로 오지 않는 상황은 해결할 수 없음

   => 5, 3600 에서 (55+5)*(55+5) 로 6이 답으로 출력되어야 하지만 괄호를 뒤에서 먼저 치는 상황을 고려할 수 없음, 무조건 순차적 진행

   => 이 경우를 고려하려면 *와 / 연산 시 이때껏 나왔던 연산의 결과들을 모두 test 해봐야함 (구현해보았더니 굉장히 오래걸림)

2. 재귀 함수로 풀 수 있을까?

   어차피 8 초과는 -1로 반환되어야하므로 재귀를 해도 8번밖에 하지 않는다. 또한 다이나믹 프로그래밍으로 재귀함수를 진행하는 와중에 이미 검사한 숫자들은 해당 수를 만들 때 들었던 N의 갯수를 찾아서 더해주면 된다. 따라서 bfs를 돌면서 연산의 결과를 모두 저장해보았음 (N과 number의 대소비교는 1과 같이 함 - 4가지 연산을 *11을 하면서 계속 시도하는 건 너무 시간복잡도가 크다고 생각함)

   => bfs로 시도해보았으나 '55/5+5/5'를 '(55+5)/5'로 축소시키는 방법을 찾으려면 answer를 출력하기 전 다른 함수를 또 구현해야해서 너무 복잡해 포기함

3. 특정한 방법을 찾기

   괄호를 해결하려면 어떻게 해야할까? 괄호를 특정 문자로 받아서 처리하는 것은 너무 복잡함 (구현해보려고 머리를 굴려보았으나 실패)

   => 괄호를 신경쓰지 않고도 모든 수를 검사해서 처리되게 해야함

   => 검사할 경우의 수는 N, NN, NNN, ... , NNNNNNNN 뿐임 (최솟값이 8번 초과로 나오면 -1 return이기 때문)

   => NNN 은 (N)(NN), (NN)(N)로 나타낼 수 있으므로 이전에 계산해두었던 값들을 가져와서 다시 계산하면 됨

 

<최종 답>

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> numbers(9, vector<int>());
vector<int> num_list;

int solution(int N, int number) {
    int num;
    int answer = 987654321;

    numbers[1].push_back(N);
    num = N * 11;
    for (int i = 2; i < 9; i++) { // 8번
        numbers[i].push_back(num);
        if (num == number && i < answer) {
            answer = i;
            break;
        }
        for (int j = 1; j < i; j++) { //4번
            int num1 = j;
            int num2 = i - j;
            for (int k = 0; k < numbers[num1].size(); k++) { 
                for (int l = 0; l < numbers[num2].size(); l++) {
                    int tmp[4];
                    tmp[0] = numbers[num1][k] + numbers[num2][l];
                    tmp[1] = numbers[num1][k] - numbers[num2][l];
                    tmp[2] = numbers[num1][k] * numbers[num2][l];
                    if(numbers[num2][l])
                        tmp[3] = numbers[num1][k] / numbers[num2][l];
                    for (int z = 0; z < 4; z++) {
                        if (find(num_list.begin(), num_list.end(), tmp[z]) == num_list.end()) {
                            num_list.push_back(tmp[z]);
                            if (tmp[z] == number && i < answer) {
                                answer = i;
                                break;
                            }
                        }
                        if (find(numbers[i].begin(), numbers[i].end(), tmp[z]) == numbers[i].end()) {
                            numbers[i].push_back(tmp[z]);
                        }
                    }
                }
            }
        }
        num = 10 * num + N;
    }
    if (answer > 8)
        answer = -1;
    return answer;
}

int main() {
    int N, number;
    cin >> N >> number;
    cout << solution(N, number);
}

3번째 생각의 흐름에 따라 특정한 방법을 찾아서 해결한 코드이다.

 간단하게 설명하자면,

 N = 5, number = 12 일 때 5는 8개까지 나올 수 있으므로 8개의 배열을 만들어 해당 수만큼의 N이 있을 때 연산으로 만들 수 있는 결과의 집합을 저장한다. 위의 그림에서 '5' 1개로 만들 수 있는 결과는 5 자신밖에 없다. 따라서 arr[1]에는 {5}를 집어넣는다. '5' 2개로 만들 수 있는 결과는 '5'로 만들 수 있는 결과를 모두 불러와 '5'로 만들 수 있는 결과와 연산하면된다. 각각 {5}밖에 없으므로 +,-,*,/ 연산을 수행하면 {55,10,0,25,1}이 '5' 2개와 사칙연산으로 만들 수 있는 수들의 집합이다. '5' 3개로 만들 수 있는 결과는 '55'의 결과집합에다가 '5'의 결과집합을 연산하면 되는데, 덧셈 곱셈이 아닌 나눗셈 뺄셈은 앞뒤 피연산자의 순서에 따라 연산 결과가 바뀌므로 '5'의 결과집합에다가 '55'의 결과집합을 연산한 결과까지 계산해준다.

 이런 식으로 계속 계산하면 되는데 여기서 주의할 점은 결과집합에 자기자신도 들어가야한다는 점과 중복된 결과가 있으면 안된다는 점이다. (안될 건 없지만 복잡도가 너무 커진다.)

 

개선할 점

 프로그래머스에서는 다 풀고나면 다른 사람의 답도 볼 수 있고, 나의 답도 자동으로 공개된다. 그래서 다른 답도 좀 훔쳐(?)봤다. 실제로 테스트 케이스 확인을 진행하던 중 130ms까지 나와서 너무 시간이 오래걸리는 것 같아서 코드를 개선해야했다.

 처음에 나온 코드는 본인과 푸는 방법은 같았으나 c++ 프로그래밍 언어 측면에서 배울 점이 많았다.

• unordered_set 이용 (정렬할 필요는 없기 때문에)

  본인은 2중 vector 구조를 이용해서 결과집합을 표현했는데 그 이유는 set으로 구현하고 싶었지만 set의 요소에 접근하는 법을 몰랐기 때문이다. 다른 코드를 보니 set 요소는 아래에 나오는 for문으로 쉽게 접근할 수 있고 set보다 정렬할 필요가 없는 unordered_set 자료구조를 이용하면 더 빠르다고 한다.

  실제로 검색해보니 unordered_set의 insert, erase, find 연산은 O(1)에 수행된다.

  원리에 대해서는 나중에 더 자세히 공부할 예정! (표시해두었다.)

• auto 타입 이용

  계속해서 습관화 되어있지 않아서인지 auto 타입을 사용하지 않는다. 하지만 별로 문제 될 것은 없어보인다.

• container의 요소 하나씩 받기

  for(int n1 : s1) // s1의 요소를 n1으로 하나씩 받기

  set도 이런 식으로 구현하면 요소를 받아올 수 있다. (iterator로 받아와도 된다)

• 최대 값 주기

  본인은 평소 987654321과 같이 주었으나 그냥 1e9라고 주면 헷갈릴 일도 없어 좋다.

 코드를 더 살펴보니 dfs를 이용한 방법도 있었다. 나는 bfs를 이용했는데 별로 상관은 없으나 이 덕분에 더 복잡하게 짜게 되어 시간이 오래걸린 것 같다. 똑같은 개념을 활용해서 dfs로 구현할 수 있다.

 이런 식으로 5와 5~5555555까지의 수를 각각 사칙연산한다. 그 결과들을 또 5~5555555까지의 수와 사칙연산한다. 사칙연산하면서 5가 몇개 들어가 있는 지는 재귀함수의 매개변수로 넘기고 해당 매개변수가 8을 넘거나 현재까지 나온 최소 경우보다 크면 그냥 return하는 기저사례를 앞부분에 삽입한다.