[ 프로그래머스 N으로 표현 (Lv3) ] (C++)

프로그래머스의 N으로 표현 (Lv3) 문제이다.

[ 문제풀이 ]

주어진 값을 숫자 'N'만으로 표현할 때, 가장 최소값을 구해야 하는 문제이다.

본인은 이 문제를 모든 경우를 다 탐색해 보는 완전탐색으로 진행해 보았다. 그 중에서도 깊이우선탐색(DFS)을 이용해서

접근해 보았다. 특히, '순열'을 구현하는 방법과 굉장히 유사한 방법으로 접근해 보았다.

먼저 우리가 뽑을 수 있는 데이터가 무엇이 있는지 부터 알아보자. 우리에게 주어지는 매개변수만 보고는 어떤 데이터를

뽑아서 순열로 구현하는지 알기가 쉽지 않다.

그래서 본인은 8칸짜리 배열을 하나 만들었다. 바로 'N'개를 이용해서 만들 수 있는 1자리 ~ 8자리 숫자들이다.

예를 들어서 N = 2라고 가정해보자. 우리가 사용할 수 있는 숫자들은 { 2, 22, 222, 2222, .... , 22222222 } 이렇게 8개가 있다.

왜 그 이상의 숫자는 사용하지 못하는 것일까 ?? 문제에서 '최솟값이 8보다 크면 -1을 return한다.' 라고 되어있다. 즉 ! 그 이상의

숫자를 만들어서 사용하는 순간, 해당 N의 숫자를 9번 이상 사용한 것이 되기 때문에 그 이상의 숫자는 의미가 없다.

이 8개의 숫자를 뽑아가면서 정답을 찾아가는 방식으로 구현하였다.

해당 숫자를 뽑는다면 우리는 총 4개의 연산을 진행할 수 있다.

"이전의 숫자 + 현재 뽑은 숫자" , "이전의 숫자 - 현재 뽑은 숫자", "이전의 숫자 * 현재 뽑은 숫자", "이전의 숫자 / 현재 뽑은 숫자"

위와 같은 4개의 연산들을 하나의 숫자를 뽑을 때 마다 진행해 주었다.

그리고 본인은 구현할 때 '괄호'에 대해서는 신경을 쓰지 않았다. 왜냐하면 '괄호'가 가지는 의미가 결국 "주어진 식에서 어떤 값을

먼저 계산하냐, 나중에 하냐"를 결정해주는 요인인데, 어차피 '완전탐색'을 이용해서 진행하였기 때문에, 어떤 값을 먼저 계산하든

나중에 계산하든 모든 경우를 다 계산하는 방식으로 구현하였기 때문에 괄호에 대한 처리를 따로 진행하지는 않았다.

[ 소스코드 ]

#include<string>
#include<vector>
 
using namespace std;
 
int Max_Cnt = 9;
int Arr[8];
 
void Make_NumberArray(int n)
{
    int Temp = n;
    for (int i = 0; i < 8; i++)
    {
        Arr[i] = Temp;
        Temp = Temp * 10;
        Temp = Temp + n;
    }
}
 
void DFS(int Cnt, int Res, int number)
{
    if (Cnt >= Max_Cnt) return;
    if (Res == number)
    {
        Max_Cnt = Cnt;
        return;
    }
    
    for (int i = 0; i < 8; i++)
    {
        int nCnt = Cnt + (i + 1);
 
        DFS(nCnt, Res + Arr[i], number);
        DFS(nCnt, Res - Arr[i], number);
        DFS(nCnt, Res * Arr[i], number);
        DFS(nCnt, Res / Arr[i], number);
    }
}
 
int solution(int N, int number)
{
    Make_NumberArray(N);
    DFS(0, 0, number);
    if (Max_Cnt == 9) Max_Cnt = -1;
    return Max_Cnt;
}