문제는 N과 사칙연산으로 number를 표현할 때, 최소 몇 개의 숫자 ‘N’이 필요한가 return하는 문제이다. 이 때 주의할 점은 기본 사칙연산 외에도 NN과 같이 사용도 가능하다는 것이다. ⇒ ex) N = 2라면, 22, 2222와 같이도 사용 가능. 각 숫자에 따라 최적의 N 갯수는 변함 없으므로 DP로 접근한다. 나는 DP로 접근하였으나, test case 8만 틀렸고.. 아직 반례를 찾지 못하여 다른 사람의 풀이를 참고하였다.
나의 풀이: 기존 구현한 dp를 바탕으로 모든 경우의 수 파악 ⇒ dp[i]가 될 수도, dp[i+1]이 될 수도 있음
다른 사람 풀이: 특정 dp[i]를 도출할 수 있는 경우의 수만 하나씩 파악
다른 사람의 풀이는 다음과 같았다. (확인해보니 나와 비슷하였다..)
dp[0 ~ 8] = set()으로 미리 세팅한다.
i = 1 ~ 8까지 조회하면서, dp[i]에 int(str(N)*i)를 넣어준다.
j = 0 ~ i 까지 일 때, 숫자1: dp[j] | 숫자2: dp[i-j]를 고른다.
+,-,*까지 해주고, 에러 방지를 위해 각 숫자가 0이 아닐 경우에만 나누기를 실행한다.
number가 dp[i]에 있으면 i를 return 한다.