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

 

 

문제

문제 설명

 

 

 

풀이

 

 

[문제 풀이] 

 

이 문제를 처음 봤을 때 횟수가 8이라 DFS로 쭉 풀어도 되겠다는 생각이 들었다.

 

DFS로 풀 경우 현재 숫자 Num과 NNN, 111과 같은 숫자들을 DFS로 연산하기만 하면 된다.

왜냐하면 N으로 특수하게 만들 수 있는 숫자들로 계산을 다 해주었기 때문에, 연산하는 과정에 다 포함이 되기 때문이다.

 

문제를 풀고 나서 다른 사람의 풀이를 보니 DP를 이용해 푼 풀이들이 보였다.

 

T번 써서 만든 숫자들 = [T-n번 써서 만든 숫자들] (사칙연산) [n번 써서 만든 숫자들]

과 같은 형태로 풀었는데, 이렇게 보니 좀 더 풀이가 깔끔해 보였다.

 

문제가 크게 어렵진 않았는데, 연산을 코드로 작성하는게 그냥 좀 오래 걸렸던 문제 같다.

 

[DP로 푸는 방법]

1. N을 T번 써서 만든 숫자들을 만들기 위해서는 N을 T-n번 써서 만든 숫자들과 N을 n번 써서 만든 숫자들을 사칙연산 해 Set에 추가하면 된다.
2. for문을 돌려 n을 1부터 T/2까지 탐색하고 T가 8일때 까지 계산한다.
3. for문으로 원하는 숫자가 T를 i번 사용한 Set에 있는지 탐색하고, 가장 숫자가 작은 i를 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> Num;
int RN;
int DFS(int num, int temp)
{
    if (temp>8)
    {
        return 0;
    }
    else
    {
        Num[num]=min(Num[num],temp);      
        int L=0,nowN;
        for (int i=1; i<=8; i++)
        {
            L+=1;
            nowN=L*RN;
            DFS(num+nowN,temp+Num[nowN]);
            if (num-nowN>0)
            {
                DFS(num-L,temp+Num[L]);
            }
            DFS(num*nowN,temp+Num[nowN]);
            if (num%nowN==0)
            {
                DFS(num/nowN,temp+Num[nowN]);
            }
            DFS(num+L,temp+Num[L]);
            if (num-L>0)
            {
                DFS(num-L,temp+Num[L]);
            }
            DFS(num*L,temp+Num[L]);
            if (num%L==0)
            {
                DFS(num/L,temp+Num[L]);                
            }
            L*=10;
        }
    }
    return 1;
}

int solution(int N, int number) {
    int answer = 0;
    Num=vector<int>(N*11111111+1,11);
    RN=N;
    int L=0;
    for (int i=1; i<=8; i++)
    {
        L+=1;
        Num[L*N]=i;
        if (i+1<=8){
            Num[L]=min(Num[L],i+1);
        }
        L*=10;        
    }
    Num[1]=min(2,Num[1]);
    DFS(0, 0);
    if (Num[number]>8)
    {
        return -1;
    }
    return Num[number];
}

 

 

Code (가지치기)

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> Num;
int RN;
int DFS(int num, int temp)
{
    if (temp>=8)
    {
        return 0;
    }
    else
    {
        if (temp+Num[1]<=8)
        {
            if (Num[num+1]>=temp+Num[1])
            {
                Num[num+1]=temp+Num[1];
                DFS(num+1,temp+Num[1]);
            }
            if (num-1>=0&&Num[num-1]>=temp+Num[1])
            {
                Num[num-1]=temp+Num[1];
                DFS(num-1,temp+Num[1]);
            }
        }        
        int L=0,nowN;
        for (int i=1; i<=8; i++)
        {
            L+=1;
            nowN=L*RN;
            if (temp+Num[L]<=8)
            {
                if (Num[num+L]>=temp+Num[L])
                {
                    Num[num+L]=temp+Num[L];
                    DFS(num+L,temp+Num[L]);
                }
                if (num-L>=0&&Num[num-L]>=temp+Num[L])
                {
                    Num[num-L]=temp+Num[L];
                    DFS(num-L,temp+Num[L]);
                }
                if (Num[num*L]>=temp+Num[L])
                {
                    Num[num*L]=temp+Num[L];
                    DFS(num*L,temp+Num[L]);
                }
                if (num%L==0&&Num[num/L]>=temp+Num[L])
                {
                    Num[num/L]=temp+Num[L];
                    DFS(num/L,temp+Num[L]);
                }
            }            
            if (temp+Num[nowN]<=8)
            {
                if (Num[num+nowN]>=temp+Num[nowN])
                {
                    Num[num+nowN]=temp+Num[nowN];
                    DFS(num+nowN,temp+Num[nowN]);
                }
                if (num-nowN>=0&&Num[num-nowN]>=temp+Num[nowN])
                {
                    Num[num-nowN]=temp+Num[nowN];
                    DFS(num-nowN,temp+Num[nowN]);
                }
                if (Num[num*nowN]>=temp+Num[nowN])
                {
                    Num[num*nowN]=temp+Num[nowN];
                    DFS(num*nowN,temp+Num[nowN]);
                }
                if (num%nowN==0&&Num[num/nowN]>=temp+Num[nowN])
                {
                    Num[num/nowN]=temp+Num[nowN];
                    DFS(num/nowN,temp+Num[nowN]);
                }
            }
            else
            {
                break;
            }
            L*=10;
        }
    }
    return 1;
}


int solution(int N, int number) {
    int answer = 0;
    Num=vector<int>(N*11111111+1,11);
    RN=N;
    int L=0;
    for (int i=1; i<=8; i++)
    {
        L+=1;
        Num[L*N]=i;
        if (i+1<=8){
            Num[L]=min(Num[L],i+1);
        }
        L*=10;
        
    }
    Num[1]=min(2,Num[1]);
    DFS(0, 0);
    if (Num[number]>8)
    {
        return -1;
    }
    return Num[number];
}

 

---

 

나는 그냥 풀었는데 DP로 푸는게 더 깔끔해 보인다.

DFS로 풀 경우 왜 풀리는지 설명하기가 좀 복잡해지는듯 하다;

 

프로그래머스