일단 인사합니다.
제가 알고리즘문제에서 시간다루는거 하고, dp문제를 제일 싫어합니다.
시간은 초를 포함시키는지 안시키는지 구별하는게 너무 빡치고,
dp는 점화식 세우는게 그냥 어려워서 빡칩니다.
하.. 근데 또 dp문제를 만났으니, 각잡고 풀어봤습니다.

일단.. 문제를 봤을 때는, 이게 dp를 사용해야하는 문제라고?
의문이 들 정도로 이상한 문제라고 느꼈습니다.
딱 보는 순간 완탐이라고 생각했죠.
근데, 완탐도 맞는 표현입니다. 이 문제는 완탐에다가 dp를 얹어서 푸는 문제입니다.
완탐 이라함은, 그냥 모든 경우의 수를 다 때려박는 문제라고하면 이해하기 쉬울겁니다.
근데 피보나치 수열 뭐시기 문제 처럼, 이미 구한 값을 다시 사용해서 경우의 수를 다시 만든다고 보시면 됩니다.

이 문제를 살펴보자면, N이라는 수로 Number를 표시하기만 하면 되는 문제입니다.
간혹, 진짜 N만으로 사칙연산으로 만들지 못하는 Number가 있지 않을 수 있냐는 질문을 할 수 있습니다.
아마 3단계까지 올라오신 분들은 그런 생각을 안하실 수 있습니다.
결론부터 말하자면, 1이상의 Number를 N만 가지고하는 사칙연산으로 전부 만들 수 있습니다. 물론 자연수입니다잉.
그이유는 N을 N으로 나누면 1이 되기 때문입니다. 1을 만들 수 있다는 말은 그 이상의 수들은 전부 만들 수 있다는 건
이해하시겠죠? (ㅎㅎ 설마.. ;;)

자, 그럼 모든 경우를 구하기만 하면, 확실히 N으로 Number값에 도달할 수 있다는 사실을 알았습니다.
N은 총 8번까지만 사용이 가능합니다. 9번부터는 경우의 수가 안드로메다로 가버려서, 아마 제한을 걸어둔 것으로 보입니다.
N의 총 사용량이 8번이 되어도, Number를 만들지 못하면, 그냥 -1을 반환시켜버리시면 됩니다.

그럼 5를 가지고 나오는 경우를 글자 사용량의 단계로 구분하여 생각해봅시다.

5를 1개 사용 - 5

• 당연한 말이지만, 5를 하나만 사용하면 5말고는 만들 수 있는 건 없습니다.

5를 2개 사용 - 55, 5*5, 5/5, 5+5, 5-5

• 2개를 사용하면, 55와 각각 5를 사칙연산을 한 값이 경우의 수가 되겠죠?

5를 3개 사용 - 555, 5*55, 5-55, 5+55, 5/55, 5*5*5, 5*(5/5), 5*(5+5), 5*(5-5), 5-(5*5), 5-(5/5) .................
55*5, 55-5, 55/5.............................. 아무튼 졸라 많습니다..

• 위의 결과에서 핵심은, 5를 추가하여 사칙연산을 하지만, 5를 1개 사용한 경우와, 5를 2개 사용한 경우를 서로 사칙연산하고, 반대로 5를 2개사용한 경우, 5를 1개사용한 경우로 순서를 다시 바꿔서 사칙연산을 수행 한 결과를 5를 3개사용한 경우라고 봐야합니다. 그 이유는, 5를 더하거나, 곱할때는, 값이 같지만, 5를 빼거나, 나눌때는 값이 무조건 달라집니다. 5-55하고, 55-5는 값이 천지차이죠, 이런걸 계산하기 위해, 순서를 바꿔서도 계산이 필요합니다.

쉽게 말하면, N을 n개사용한 경우의 수는 그 이전에 미리 계산된 경우에서 n개의 수를 만들 수 있는 모든 조합을 계산해야한다는 말입니다. N이 7번 사용된 경우를 구할려면,

(1번 경우, 6번 경우), (2번 경우, 5번 경우), (3번 경우, 4번 경우), (4번 경우, 3번경우), (5번 경우, 2번 경우), (6번 경우, 1번경우)

위와 같이 7이라는 수를 조합할 수 있는 모든 경우를 계산해주면 됩니다.
(1번 경우와, 6번 경우)의 의미는 N을 한번 사용한 경우를 피연산자, N을 6번 사용한 경우를 연산자라고 생각하고 계산하라는 의미이다.
dp[1] = 5, dp[6] = 5, 10, 0, 20, 50 ................. 와 같이 있다고 하면,

dp[7] = 5*5, 5+5, 5-5, 5/10, 5 * 10, 5+10 ..... 등 2중 반복 연산이 수행된다.

위의 방식대로 계산되면, 아래와 같은 의문은 해결된다.

의문1) 555+55가 계산되는 부분이 발생하는가?
위의 의문은 같은 숫자가 연속적으로 나열된 부분에서, 연산자로 구별된 부분에서 연속된 수끼리의 사칙연산을
계산 되어지는 지에 대한 여부가 궁금한 것이다.
N이 5번 사용된 경우이므로 dp[3] 과 dp[2]의 조합으로 인해, 555와 55는 반드시 계산될 것이다.

위의 의문을 품어본 사람이 있으면 위에서 굳이 n이 되는 모든 경우를 순서를 뒤바꿔면서 연산을 진행하는지 이해가 될 것이다.

dp[n]는 N을 n개 만큼 사용한 경우의 수를 담는 변수가 된다.
동적배열이나, 리스트의 형태가 각각의 요소가 될 것이다.

한 번의 연산이 모두 끝나면, 나온 결과 중에 number있는지 확인하는 연산을 필히 수행하여, 원하는 결과를 도출하자.
8번을 전부 돌아도, number비교가 fail될 경우 답은 -1을 명심하자.
또한 피연산자에는 0이 있어도 상관없지만, 연산자는 반드시 0이 와서는 안된다. 또한 나머지는 다 버리는 연산을 수행한다.
0을 제외시킬 대는 연산자의 값이 0이 못들어오게 막거나, try문을 사용하여도 좋다.

도움이 되었으면 좋겠습니다.
추가적으로 해시를 통해 중복제거를 사용하면, 시간을 좀 더 빠르게 할 수 있다.