https://school.programmers.co.kr/learn/courses/30/lessons/154538
๋ฌธ์ ์ค๋ช
์์ฐ์ x๋ฅผ y๋ก ๋ณํํ๋ ค๊ณ ํฉ๋๋ค. ์ฌ์ฉํ ์ ์๋ ์ฐ์ฐ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- x์ n์ ๋ํฉ๋๋ค
- x์ 2๋ฅผ ๊ณฑํฉ๋๋ค.
- x์ 3์ ๊ณฑํฉ๋๋ค.
์์ฐ์ x, y, n์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, x๋ฅผ y๋ก ๋ณํํ๊ธฐ ์ํด ํ์ํ ์ต์ ์ฐ์ฐ ํ์๋ฅผ returnํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ด๋ x๋ฅผ y๋ก ๋ง๋ค ์ ์๋ค๋ฉด -1์ return ํด์ฃผ์ธ์.
๋ด ํ์ด
์ฒซ๋ฒ์งธ ํ์ด
dfs
#include <string>
#include <vector>
using namespace std;
int Answer = -1;
void dfs(int x, int y, int n, int count)
{
if(x == y)
{
if(Answer == -1 || Answer > count)
Answer = count;
return;
}
else if(x > y)
return;
dfs(x+n, y, n, count+1);
dfs(x*2, y, n, count+1);
dfs(x*3, y, n, count+1);
}
int solution(int x, int y, int n) {
dfs(x, y, n, 0);
return Answer;
}
์๊ฐ์ด๊ณผ,,,
๋๋ฒ์งธ ํ์ด
dp
๋ชฉํ ์ซ์ Y ๋ถํฐ ์์ ์ซ์ X๊น์ง ์ด๋ํ๋ฉด์ ์ต์ ์ด๋ ํ์๋ฅผ ๊ตฌํ๋ค.
#include <string>
#include <vector>
#include <memory.h>
using namespace std;
int solution(int x, int y, int n) {
int dp[1'000'001];
memset(dp, 1'000'001, 1'000'001 * sizeof(int));
dp[y] = 0;
for(int i = y; i > x; --i)
{
if(i-n > 0)
dp[i-n] = min(dp[i-n], dp[i]+1);
if(i%2 == 0)
dp[i/2] = min(dp[i/2], dp[i]+1);
if(i%3 == 0)
dp[i/3] = min(dp[i/3], dp[i]+1);
}
if(dp[x] >= 1'000'001)
dp[x] = -1;
return dp[x];
}
'๐ฅ๏ธ Study Note > Coding Test' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค]level.2 - ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ ์ฐพ๊ธฐ(C++) (0) | 2023.09.28 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค]level.3 - ๋ค๋จ๊ณ ์นซ์ ํ๋งค (C++) (0) | 2023.09.26 |
[ํ๋ก๊ทธ๋๋จธ์ค]level.2 - ๋ฐฉ๋ฌธ ๊ธธ์ด (C++) (0) | 2023.09.21 |
[ํ๋ก๊ทธ๋๋จธ์ค]level.3 - ๋ณด์ ์ผํ (C++) (0) | 2023.09.20 |
[ํ๋ก๊ทธ๋๋จธ์ค]level.3 - ๋ฑ์ฐ์ฝ์ค ์ ํ๊ธฐ (C++) (1) | 2023.09.18 |