[Programmers] N으로 표현

문제 : https://programmers.co.kr/learn/courses/30/lessons/42895

---

DP 관련 문제이니 DP로 풀어야겠는데 number를 인덱스로 dp 배열을 만드려고하니 막막하다.

막힐때는 제한사항을 보면서 문제 제작자의 의도를 파악해보자.

 

제한사항

1. 1 <= N <= 9

2. 1 <= number <= 32,000

3. 괄호, 사칙연산만 가능. 나누기 연산에서 나머지는 무시.

4. 최소값이 8보다 크면 -1을 반환

 

사칙연산과 N을 대입하면서 number가 인덱스인 배열을 채우려면 적어도 O(N^number) 정도의 시간이 걸릴텐데 TLE가 발생할것이다.

여기서 사용할만한 조건은 4번이다. 최소값이 8보다 크면 -1을 반환한다는 이야기는 N을 최대 8번까지만 사용한다는 뜻이다. 이건 사용할만하다.

dp[cnt] = N을 cnt번 사용해서 만들 수 있는 수들의 집합 인 배열을 만들어서 채워보자. cnt <= 8 이 될것이다.

 

example) N=5, cnt = 3

dp[1] = {5}, dp[2] = {0, 1, 10, 25, 55}

1. N을 i번 이어붙이기. 
     ex) 555

2. dp[i] + dp[cnt-i] 들의 집합. (1 <= i < cnt) 
     ex) dp[1] + dp[2] => dp[3] = {5, 6, 15, 30, 60}

3. |dp[i] - dp[cnt-i]| 들의 집합. 
     ex) |dp[1] - dp[2]| => dp[3] = {4, 5, 20, 50}

4. dp[i] * dp[cnt-i] 들의 집합.
     ex) dp[1] * dp[2] => {0, 5, 50, 125, 275}

5. dp[i] / dp[cnt-i], dp[cnt-i] / dp[i] 들의 집합. (분모가 0이 아닌 경우)
     ex) dp[1] / dp[2] => {5, 0}
         dp[2] / dp[1] => {0, 2, 5, 11}

 

위 방식대로 모든 dp배열을 채웠을때, dp 배열을 앞에서부터 탐색하면서 number가 있는지 탐색한다.

만약 가장 먼저 number가 있는 dp 배열인덱스가 i 라면 i 가 정답이된다.

모든 dp 배열 을 탐색했을때 number를 찾을 수 없다면 -1을 반환한다.

 

시간복잡도는.. 얼마일까..

사실 시간복잡도에 사용할 변경되는 변수들이 이 알고리즘엔 없다.

N에 따라서 dp 배열의 크기는 살짝씩 달라질 수 있지만 결국엔 dp[8] 크기를 채우게 될거고 이 배열은 기존에 구한 dp배열들의 수들의 계산값이 저장된다. 그래서 O(1) 로 봐도 좋지 않을까.

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/DP/N%EC%9C%BC%EB%A1%9C%20%ED%91%9C%ED%98%84.cpp