๐ ํ๋ก๊ทธ๋๋จธ์ค / ์ฐ์ต๋ฌธ์ / Level 2 / ์ซ์ ๋ณํํ๊ธฐ
๐ ๋ฌธ์
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๐ซ ์ ํ ์ฌํญ
- 1 ≤ x ≤ y ≤ 1,000,000
- 1 ≤ n < y
๐ ์ ์ถ๋ ฅ ์
| x | y | n | result |
| 10 | 40 | 5 | 2 |
| 10 | 40 | 30 | 1 |
| 2 | 5 | 4 | -1 |
๐ค ํ์ด ๋ฐฉ๋ฒ
1๏ธโฃ ์๊ฐ ์ ๋ฆฌ (1) - PASS
โก๏ธ x ์์ ์ถ๋ฐํ์ฌ y ๋ฅผ ๋ง๋ค๊ธฐ ๊น์ง์ ๊ฒฝ์ฐ๋ฅผ ํฌ๊ฒ 3๊ฐ์ง๋ก ๋๋์ด ๋ณผ ์ ์๋ค.
โ Only ๊ณฑ์ผ๋ก๋ง
โก Only ํฉ์ผ๋ก๋ง
โข ํฉ & ๊ณฑ ๋ชจ๋ ์ฌ์ฉ
โก๏ธ ์ด๋ ์ซ์์ ๊ทผ์ ํ๊ธฐ ์ข์ ๋ฐฉ๋ฒ์ ์๋ฌด๋๋ ๊ณฑ์ด์ง๋ง ๋ํ๊ธฐ์ ์ ๊ณต๋ n ์ด ์๊ฐ๋ณด๋ค ํฐ ์ ์ผ ๋๋ ๋ํ๊ธฐ๊ฐ ๋ ํจ์จ์ ์ผ ์ ์๋ค. ๋ฐ๋ผ์ ์ํฉ์ ๋ฐ๋ผ ๊ฒฐ๊ณผ๋ฅผ ๋น๊ตํ ํ์๊ฐ ์๋ค.
2๏ธโฃ ์๊ฐ ์ ๋ฆฌ (2) - DFS
โ ๊ธฐ๋ณธ ์์ด๋์ด
โก๏ธ ์๊ฐํด๋ณด๋ x ์์ y ๋ก ํค์๋๊ฐ๊ธฐ ๋ณด๋ค๋ y ์์ x ๋ก ์ค์ฌ๋๊ฐ๋ ๊ฒ์ด ํฉ & ๊ณฑ์ ์๊ฐํ๊ธฐ ํธํ ๊ฒ ๊ฐ์๋ค. ์์ 2 ๋ฅผ ๊ทธ๋ฆผ์ผ๋ก ํํํด๋ณด๋ฉด,

โก๏ธ ์์ ๊ฐ์ด ํํ ๊ฐ๋ฅํ๋ฐ, ๊ฑฐ๊พธ๋ก ๋ด๋ ค๊ฐ ๊ฒฝ์ฐ %2, %3, -n ์ค์ ๊ฐ๋ฅํ ์ฐ์ฐ์ด ๋ฐ๋ก ํ์ธ์ด ๊ฐ๋ฅํ๋ฏ๋ก x ์์ y ๋ก ํค์๋๊ฐ๋ ๊ฒ ๋ณด๋ค ํจ์จ์ ์ผ๋ก ํ๋จ์ด ๊ฐ๋ฅํ๋ค.
โก ์ฝ๋ ์์ฑ
โก๏ธ ์ ์์ด๋์ด๋ DFS ๋ผ๊ณ ๋ณผ ์ ์์ ๊ฒ ๊ฐ๋ค. ๋ฐ๋ผ์ ์๋์ ๊ฐ์ด ํจ์๋ฅผ ์์ฑํ์๋ค.
public static void dfs (int y, int depth, int calc) {
// ๋ถ๋ถ โ
switch (calc) {
case 0 :// %2
if (y % 2 != 0) return;
y /= 2;
break;
case 1 : // %3
if (y % 3 != 0) return;
y /= 3;
break;
case 2 : // - n
if (y-nn < goal) return;
y -= nn;
break;
}
// ๋ถ๋ถ โก
if (y == goal) {
if (answer > 0) {
answer = Math.min(answer, depth);
return;
}
answer = depth;
return;
}
// ๋ถ๋ถ โข
dfs (y, depth+1, 0);
dfs (y, depth+1, 1);
dfs (y, depth+1, 2);
return;
}
๋ถ๋ถ โ
โก๏ธ %2 / %3 / -n ์ค ์ด๋ค ์ฐ์ฐ์ ํด์ผํ๋์ง ํ์ธํ๊ธฐ ์ํด switch ๋ฌธ์ ์ฌ์ฉํ์๋ค.
๋ถ๋ถ โก
โก๏ธ ์ฐ์ฐ ๋ค์๋ ๋ชฉํํ๋ ๊ฐ (x) ์ ๋ณ๊ฒฝ๋ ๊ฐ y ๊ฐ ๊ฐ์์ง ํ์ธํ๊ณ , ๊ฐ์ ๊ฒฝ์ฐ ๊ธฐ์กด ์ต์๊ฐ๊ณผ ๋น๊ตํ์ฌ ๋ ์์ ๊ฐ์ ์ ์ฅํ๋ค.
๋ถ๋ถ โข
โก๏ธ ๋ณ๊ฒฝ๋ ๊ฐ y ๊ฐ ๋ชฉํํ๋ ๊ฐ (x) ๊ณผ ๊ฐ์ง ์์ ๊ฒฝ์ฐ ๋ค์ ๊น์ด๋ก ๋ค์ด๊ฐ๋ค.
โข ๊ฒฐ๊ณผ

โก๏ธ ํ ์คํธ ์ฝ๋๋ ํต๊ณผํ์์ง๋ง, ์ ํ์ฑ ํ ์คํธ๋ฅผ ์คํ์์ผ๋ณด๋ฉด ์๊ฐ ์ด๊ณผ๋ก ์คํจํ๋ ์ผ์ด์ค๊ฐ ๋ง์ด ์๋ค. ์๊ฐํด๋ณด๋ x ์ y ๊ฐ์ ์ฐจ์ด๊ฐ ํฌ๋ฉด์ n ์ด 1 ์ผ ๊ฒฝ์ฐ DFS ๋ฅผ ์คํํ๋ฉด ์๊ฐ ๊ด์ ์์ ๋นํจ์จ์ ์ผ ์ ์์ ๊ฒ์ด๋ผ๋ ์๊ฐ์ด ๋ค์๋ค.
โฃ ๊ฐ์ (1)
โก๏ธ ์๊ฐ์ด๊ณผ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด์ depth ๊ฐ answer ๋ณด๋ค ๊น๊ฒ ๋ค์ด๊ฐ๋ฉด ๋ ์ด์ ์ฐ์ฐ์ ์งํํ์ง ์๊ณ ์ข ๋ฃํ๋๋ก ์ฝ๋๋ฅผ ์ถ๊ฐํ์๋ค. ์ด์ฒํผ ๊ณฑํ๊ธฐ๋ ๋ํ๊ธฐ๊ฐ ๋ช ๋ฒ ๋์ค๋์ง๋ ์ค์ํ ๋ฌธ์ ๊ฐ ์๋๊ธฐ ๋๋ฌธ์ ์ต์๊ฐ๋ง ํ์ธํ๋๋ก ํ์๋ค.
if (answer > 0 && depth >= answer) return;

โก๏ธ ๊ทธ ๊ฒฐ๊ณผ ์๊ฐ์ด๊ณผ๋ก ์คํจํ๋ ๋๋ถ๋ถ์ ํ ์คํธ ์ผ์ด์ค๋ค์ ํต๊ณผํ ์ ์์๋ค. ์ด์ 6๋ฒ๊ณผ 11๋ฒ ํ ์คํธ์ ์คํจ ์์ธ์ ์๊ฐํด๋ณด์์ผํ๋ค.
โฃ ๊ฐ์ (2)
โก๏ธ 6๋ฒ์ด ํ๋ฆฌ๋ ์ด์ ๋ ์๊ฐ๋ณด๋ค ๋จ์ํ๋ค. x == y ์ธ ๊ฒฝ์ฐ์์ผ๋ก 0 ์ ๋ฆฌํดํด์ฃผ๋ฉด ๋๋ค.
if (x == y) return 0;
โก๏ธ 11๋ฒ๋ง ํต๊ณผํ๋ฉด ๋์ธ๋ฐ ๊ฐ์ ์ ์ ์์ง ๋ ์ฐพ์ง ๋ชปํ๋ค.
๐ป ํ์ด ์ฝ๋
class Solution {
public static int goal;
public static int nn;
public static int answer = -1;
public int solution(int x, int y, int n) {
// ์ ์ ๋ณ์ ์ด๊ธฐํ
goal = x;
nn = n;
// ์์ธ์ฒ๋ฆฌ : ๋ ์๊ฐ ๊ฐ์ ๊ฒฝ์ฐ
if (x == y) return 0;
dfs (y, 1, 0);
dfs (y, 1, 1);
dfs (y, 1, 2);
return answer;
}
public static void dfs (int y, int depth, int calc) {
// ์ต์๊ฐ๋ง์ ํ์ธํจ
if (answer > 0 && depth >= answer) return;
switch (calc) {
case 0 :// %2
if (y % 2 != 0) return;
y /= 2;
break;
case 1 : // %3
if (y % 3 != 0) return;
y /= 3;
break;
case 2 : // - n
if (y-nn < goal) return;
y -= nn;
break;
}
// ๋ชฉํ๊ฐ์ ๋๋ฌํ ๊ฒฝ์ฐ
if (y == goal) {
if (answer > 0) {
answer = Math.min(answer, depth);
return;
}
answer = depth;
return;
}
dfs (y, depth+1, 0);
dfs (y, depth+1, 1);
dfs (y, depth+1, 2);
return;