N으로 표현 42895

문제

접근 방법

N를 1번 쓴 경우
N
2번 쓴 경우
N*N, N/N, N+N, N-N, NN
3번 쓴 경우 일단 NN은 생략
(N*/+-N)*/+-N, N*/+-(N*/+-N)
4번 쓴 경우
(N*/+-N)*/+-(N*/+-N), ((N*/+-N)*/+-N)*/+-N, N*/+-((N*/+-N)*/+-N)
이전 결과가 다음 결과에 쓰인다는 것을 알 수 있다.
중복된 결과가 나올 테니 set을 사용하는 게 좋다.

코드

#include <vector>
#include <set>
using namespace std;
int solution(int N, int number)
{
    if (N == number)
        return 1;
    set<int> dp[8];
    int NN = 0;
    for (int i = 0; i < 8; ++i)
    {
        NN = NN * 10 + N;
        dp[i].insert(NN);
    }
    for (int i = 1; i < 8; ++i)
    {
        for (int j = 0; j < i; ++j)
            for (int k : dp[j])
                for (int l : dp[i - j - 1])
                {
                    dp[i].insert(k * l);
                    dp[i].insert(k + l);
                    dp[i].insert(k - l);
                    if (l != 0)
                        dp[i].insert(k / l);
                }
        if (dp[i].find(number) != dp[i].end())
            return i + 1;
    }
    return -1;
}

풀이

이어 붙인 경우와 사칙연산의 경우를 집어넣고 조합하면 된다. 0으로 나누면 안 되기에 해당 경우를 제외해주면 된다.