1. ๋ฌธ์ ์ค๋ช
N๊ณผ number๊ฐ ์ฃผ์ด์ก์ ๋, ์ฌ์น์ฐ์ฐ์ ํ์ฉํด number๋ฅผ ๋ํ๋ผ ์ ์๋ N์ ์ต์ ๊ฐ์๋ฅผ ๊ตฌํด๋ผ
2. ์ ๊ทผ ๋ฐฉ์
(1) ์๋ชป ์ ๊ทผ ํ๋ ๋ฐฉ์
KEY WORD
: BFS
๋ฐฑ์ค์์ ์์ฃผ ํ๋ ์ฐ์ฐ ๊ท์น์ด ์ฃผ์ด์ก์ ๋, target ๊ฐ์ ๋ช ๋ฒ๋ง์ ๋ง๋ค ์ ์๋์ง ๊ตฌํ๋ ๋ฌธ์ ๋ผ๊ณ ์๊ฐํ๋ค. ์๋ฅผ ๋ค์ด+2, x5 -1์ด ๊ฐ๋ฅํ๋ค๊ณ ํ ๋, A๋ฅผ B๋ก ๋ง๋๋ ์ต์ ๊ฒฝ์ฐ ์์๋?
๊ฐ์ ๋ฌธ์ ๋ง์ด๋ค.
ํด๋น ๋ฌธ์ ๋
- ๋ฌธ์ ์ ์ต๋ ๋ฒ์๊น์ง 1์ฐจ์ ๋ฐฐ์ด์ ๋ง๋ ๋ค. (๋ฌธ์ ๋ฒ์๊ฐ 1<= B <= 32000 ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 32001)
๋ฐฐ์ด์ index๋ ์ซ์, value๋ ํด๋น ์ซ์๋ฅผ ๋ง๋ค ์ ์๋ ์ต์ ์ฐ์ฐ ์ ์ด๋ค. - start ๊ฐ์ธ A๋ถํฐ ์์ํด์, ์ฐ์ฐ์ ํ์ฉํด ๋ค๋ฅธ ๊ฐ index๋ก ์ด๋ํ๋ค.
๋ง์ฝ A = 2์ด๋ฉด, 2๋ก ๋ง๋ค ์ ์๋ ๋ค๋ฅธ ์๋, 4, 10, 1 ์ผ ๊ฒ์ด๋ค. ์ด์ ํด๋น ์๋ฅผ index๋ก ๊ฐ์ง๋ ์์์ value๋ ํ ๋ฒ์ ์ฐ์ฐ์ผ๋ก ๊ฐ์ ๊ตฌํ์์ผ๋ก, 2๊ฐ ๋๋ค.
ํด๋น ๋ฐฉ์์ด ํ๋ ธ๋ ์ด์
๋ด๊ฐ ์์๋ก ๋ค์๋ ๋ฌธ์ ์์๋ ํด๋น ๋ฐฉ์์ด ํตํ๋ค. ์ด์ ๋ ์ฐ์ฐ ๋ฐฉ์๊ณผ ํผ์ฐ์ฐ์๊ฐ ๊ณ ์ ๋์ด ์๊ธฐ
๋๋ฌธ์ด๋ค.
ํ์ง๋ง ๋ด๊ฐ ํ์ด์ผ ํ๋ N์ผ๋ก ํํ์์๋ ์ํฉ์ด ๋ค๋ฅด๋ค. N = 5
์ผ ๊ฒฝ์ฐ, N= 1์ ๊ฒฝ์ฐ ์ค ํ๋
์ N=4์ ๊ฒฝ์ฐ ์ค ํ๋
, N=2์ ๊ฒฝ์ฐ ์ค ํ๋
์ N=3์ ๊ฒฝ์ฐ ์ค ํ๋
๋ก ์ต์ ํ์๊ฐ 5์ธ ์๋ฅผ ๋ง๋๋ ๋ฑ ์กฐํฉ์ด ๋ค์ํ๊ธฐ ๋๋ฌธ์ด๋ค. ์ด ๋๋ฌธ์ ์์ ๊ฐ์ด ๋ฐฐ์ด๋ก ๋ฌธ์ ๋ฅผ ํผ๋ค๋ฉด, BFS ์ฒซ wave์์ ๋์จ ์๋ค์ ๋ค์ ๊ณ์ฐ์์ ๋ ์ฐพ์๋ด์ ๋ชจ๋ ๋ค์ ๊ณ์ฐ์ ํ์ฉ ํด์ผ ํ๋ค. ํ์ ์๊ฐ ๋ฐ ํ์ํ ๊ฐ๋ค์ ๋ํ ์กฐํฉ(O(2^n))์ผ๋ก ๋ฌธ์ ๋ฅผ ํธ๋ ๋ฑ ์๊ฐ์ด ์ค๋ ๊ฑธ๋ฆฐ๋ค.
(2) ์ ๋๋ก ๋ ํ์ด ๋ฐฉ์
KEY WORD
: DP
DP๋ ๋๋ํ ์์ ํ์
์ด๋ผ๋ ์ด๋ช
์ด ์๋๋ฐ, ํด๋น ๋ฐฉ๋ฒ์ ์ด ํ์ด ๋ฐฉ์์ผ๋ก ํ๋๋ผ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ค ๊ตฌํ๋ ๋ฌด์ํ ๋ฐฉ๋ฒ์ ์จ์ ์ ๋ง DP๋ผ๊ณ ๋ถ๋ ค๋ ๋๋์ง ๋ชจ๋ฅด๊ฒ ๋ค. ํธ๋ ๋ฐฉ์์ ๋ค์๊ณผ ๊ฐ๋ค.
- DP ๋ฐฐ์ด์ ๋ง๋ ๋ค.
DP ๋ฐฐ์ด์index
= ์ฌ์ฉํ N์ ๊ฐ์,value
= ํด๋น N์ ๊ฐ์๋ก ๋ง๋ค ์ ์๋ ๋ชจ๋ ์๋ฅผ set์ผ๋ก ์ ์ฅ ์ด๋ค. - DP[1]์ ๋น์ฐํ N ์์ ๋ฐ์ ์๋ค.
- DP[2]๋ฅผ ์๊ฐํด๋ณธ๋ค๋ฉด,
NN ๋ฌธ์์ด
ํ์์ ๊ฐ ํ๋ +N 2๊ฐ ๊ฐ์ ์ฌ์น์ฐ์ฐ
๋ฐฉ์ ์ผ ๊ฒ์ด๋ค. - DP[3]์ ๋ง์ฐฌ๊ฐ์ง๋ก,
NNN ํ์
๋ฌธ์์ด ํ๋,N=1
์N=2
๋ฅผ ํ์ฉํด ๋์ฌ ์ ์๋ ๊ฐ์ผ ๊ฒ์ด๋ค.
(โป ์ฃผ์์ : A +*/- B ์ผ ๋,N=1
๊ณผN=2
๋ฅผ ์์ชฝ ๋ฒ๊ฐ์ ์ฌ์ฉํด์ผํ๋ค. ์๋ํ๋ฉด, ๋นผ๊ธฐ์ ๋๋๊ธฐ์ ๊ฒฝ์ฐ ์์์ ๋ฐ๋ผ ๊ฐ์ด ๋ค๋ฅด๊ธฐ ๋๋ฌธ์ด๋ค. ์ค๋ณต ๊ฐ์ set์ด ๊ฑธ๋ฌ์ฃผ๋๊น ๊ฑฑ์ ๋ง์.) - ์ด๋ฐ ์์ผ๋ก ์ญ ๊ฐ๋ฉด DP[i]๋
N์ i๋ฒ ์ด์ ๋ฌธ์์ด
+DP[i-k]
์DP[k]
์ซ์๋ค ๊ฐ์ ์ฌ์น์ฐ์ฐ ๋ฐฉ์ ์ผ ๊ฒ์ด๋ค.
(1<= k < i)
N์ ํ ๊ฐ ์ด์ฉํ ๊ฒฝ์ฐ๋ถํฐ ์ฐจ๋ก๋๋ก ๊ฐ๋ ๊ฒ์ด๊ธฐ ๋๋ฌธ์, ๊ฐ์ฅ ์ต์์ N๋ง ์ด์ฉํด์ ์ซ์๋ค์ ๋ง๋ค์ด๋ด๊ณ ์๋ค. ๋ฐ๋ผ์ ๊ฐ์ ๋ง๋ค๋ค๊ฐ target ๊ฐ์ธ number๊ฐ ๋์๋ค๋ฉด ๊ฑฐ๊ธฐ์ loop๋ฅผ ์ข
๋ฃํ๊ณ ๋ฌธ์ ๋ฅผ ๋๋ด๋ฉด ๋๋ค.
๋ต์ ๊ฐ์ ๋ฌด์กฐ๊ฑด ๋์จ๋ค. ์๋ํ๋ฉด N/N์ด 1์ธ ๊ฒ์ ์ด์ฉํ๋ฉด, 1์ ๋ํ๊ณ ๋นผ๋ ์์ผ๋ก ์ด๋ป๊ฒ๋ target๊ฐ์ด ๋ฌด์์ด๋ ์ง ๋ง๋ค ์ ์๊ธฐ ๋๋ฌธ์ด๋ค.
์ด๋ฐ ํ์ด๋ ์๊ฐ์ด ๊ฝค ์ค๋ ๊ฑธ๋ฆด ๊ฑฐ ๊ฐ์๋ฐ ๊ด์ฐฎ๋์? ๐ค
๊ด์ฐฎ๋ค. ์ด์ ๋ ๋ค์ 2๊ฐ์ง ์ด์ ์์๋ค.
- N=8 ์ด๊ณผํ์ฌ ๊ณ์ฐ๋๋ ์๋ ๋ชจ๋ -1๋ก ์ฒ๋ฆฌํ๋ผ๊ณ ํด์, ์ฐ๋ฆฌ๋ N=1๋ถํฐ N=8๊น์ง๋ง ์ฒ๋ฆฌํ๋ฉด ๋๋ค.
- ๊ณ์ฐํด์ผํ ์์ด ๊ธฐํ๊ธ์์ ์ด์ง ์๋ค.
N = 1์ผ ๋, ๊ณ์ฐ ์์
N = 2์ผ ๋, 4์น์ฐ์ฐ 4๊ฐ์ง + NN ํด์ 5๊ฐ
N = 3 ์ผ ๋, N=2(5๊ฐ์ง) ์ N=1(1๊ฐ์ง)์์ ๋์จ ๊ฐ๋ค ๊ฐ์ ์ฌ์น์ฐ์ฐ(20๊ฐ์ง) + NNN 1๊ฐ
...
3. ์ฝ๋ ๋ถ์
import java.util.*;
import java.io.*;
class Solution {
// ๋๋๊ธฐ๋ฅผ ํตํด 1์ ๋ง๋ค ์ ์๊ธฐ์, number๊ฐ 1~ 32000 ์ค ๋ญ๋ ๊ฐ์ ๊ฒฐ๊ตญ์ ๋ง๋ค ์ ์๋ค.
// ํ์ง๋ง ๋ฌธ์ ์์๋ N ๋ฑ์ฅํ์๊ฐ 8๋ณด๋ค ํฌ๋ฉด ๊ทธ๋ฅ -1๋ก ์ถ๋ ฅํ๋ผ๊ณ ํ๋ค. ์ด ์์ ์์ N ๋ฑ์ฅํ์๊ฐ 8๋ฒ ์ดํ์ธ ๋
์๋ค๋ง ๊ณ์ฐํ๋ฉด ๋๋ค๋ ๊ฒ์ด๋ค.
/*
dp[k] ๋ N์ K๋ฒ ์ฌ์ฉํ ๊ฐ๋ค์ ๋ชจ์ (dp ์์๋ง๋ค set์ผ๋ก ๊ฐ์ ๋ชจ์๋์ ๊ฒ์.)
dp[k] ๋ dp[l] ์ dp[k-l] ์ ์กฐํฉ์ผ๋ก ๋์ค๋ ๋ชจ๋ ์ (1 <= l < k)
*/
public int solution(int N, int number) {
if(N == number) return 1;
// 0. ๊ฐ ์ด๊ธฐํ
Set<Integer> [] dp = new Set [9];
for(int i = 1; i < 9; i++){
dp[i] = new HashSet<>();
}
// 1. dp[1]๋ถํฐ dp[8]๊น์ง ์ฐจ๊ทผ์ฐจ๊ทผ ๊ณ์ฐ
dp[1].add(N);
int accN = N;
for(int i = 2; i< 9; i++){
accN = accN*10+N;
if(accN == number) return i;
dp[i].add(accN);
for(int j = 1; j < i; j++){
for(int k : dp[j]){
for(int l : dp[i-j]){
int p = k+l; int s = k-l; int m = k*l; int d = l >0? k/l : 0;
if( p == number || s == number || m == number || d == number) return i;
dp[i].add(p);
dp[i].add(s);
dp[i].add(m);
if(d != 0) dp[i].add(d);
}
}
}
}
return -1;
}
}
4. ์๋ชป ์ ๊ทผ ํ๋ ์ฝ๋
import java.util.*;
import java.io.*;
class Solution {
// all ๋ฐฐ์ด: index = ์ซ์, value = ํด๋น ์ซ์๋ฅผ ๋ง๋ค๊ธฐ ์ํด ์ฐ์ธ N์ ์ต์ ๊ฐ์
// ์๊ฐํด์ค์ผ ํ ๊ฒ:
// 1.N์ ์ค๋ณตํด์ ์ ์ ๋ฌธ์์ด์ ํ์ฉํ๋ฉด ๋ ์ต์๋ก ์ค์ผ ์ ์๋๊ฐ?
// 2. ์ฌ์น์ฐ์ฐ๊ณผ N์ ํ์ฉํ๋ฉด ๋ ์ต์๋ก ์ค์ผ ์ ์๋๊ฐ?
public int solution(int N, int number) {
// 0. ๊ฐ ์ด๊ธฐํ
int [] all = new int [32001];
Arrays.fill(all, Integer.MAX_VALUE);
ArrayDeque<Integer> aq1 = new ArrayDeque<>();
// 1. NN ํ์ ๋ฌธ์์ด์ ํ์ฉํ์ฌ, ๋ง๋ค ์ ์๋ ์ซ์์ ์ต์ ํ์ ๊ตฌํด์ queue์ ๋ฃ๊ธฐ -> ์ด๊ฑธ๋ก ์ฌ์น์ฐ์ฐ ํ์ฉ
int temp = N;
int c = 1;
while(temp <= 32000){
all[temp] = c++;
aq1.add(temp);
temp = temp*10+N;
}
// 2. ์ฌ์น์ฐ์ฐ๊ณผ N ํ์ฉํ์ฌ ์ซ์ ๋ง๋๋ ์ต์ ํ์ ๊ตฌํ๊ธฐ
while(!aq1.isEmpty()){
// nV = ์ซ์, nC = N์ผ๋ก ๊ทธ ์ซ์๋ฅผ ๋ง๋ค ์ ์๋ ํ์
int nV = aq1.poll();
int nC = all[nV];
int temp2 = N;
// N์ ์ด์ด๋ถ์ธ ๊ฐ๋ค์ ๊ฐ์ง๊ณ ์ฌ์น์ฐ์ฐํด์ ์ต์๋ก ๊ฐ ์ ์๋ ํ์๋ฅผ ์
๊ฑฐ์
while(temp2 <= 32000){
// temp2 = N์ ์ด์ด๋ถ์ธ ์ซ์ ์ด๊ฑธ๋ก ์ฌ์น์ฐ์ฐ GO
for(int i = 0; i < 6; i++){
int now = 0;
switch(i) {
case 0: {now = nV + temp2; break;}
case 1: {now = nV - temp2; break;}
case 2: {now = nV * temp2; break;}
case 3: {now = nV / temp2; break;}
case 4: {now = temp2 - nV; break;}
case 5: {now = temp2 / nV; break;}
}
// now๊ฐ ๋ฒ์๋ฅผ ๋๊ฑฐ๋, now๋ฅผ ๋ง๋ ํ์๊ฐ ์ด๋ฏธ ์๋ ํ์๋ณด๋ค ํฌ๋ฉด ๋์ด๊ฐ๊ธฐ
if(now <= 0 || now > 32000 ||
temp2 > 32000 || temp2 < 0 || all[now] < nC + all[temp2]) continue;
// ์ต์๊ฐ ์๋ก ๊ฐฑ์ ํ์ ์์๋ง queue์ ๋ฃ๊ณ ๋ค์ ๊ณ์ฐ ๋๋ฆฐ๋ค.
all[now] = nC + all[temp2];
aq1.add(now);
}
temp2 = temp2*10+N;
}
}
return all[number] > 8? -1 : all[number];
}
}
์ด์ N๋ค์ ํ์ฉํ ์กฐํฉ์ ํตํ ๋ฉ๋ชจ์ด์ ์ด์ ์ ์๊ฐ์น ๋ชปํ๋ค.