ํผ๋ณด๋์น ์๋ F(0) = 0, F(1) = 1์ผ ๋, 1 ์ด์์ n์ ๋ํ์ฌ F(n) = F(n-1) + F(n-2) ๊ฐ ์ ์ฉ๋๋ ์ ์ ๋๋ค.
์๋ฅผ ๋ค์ด
์ ๊ฐ์ด ์ด์ด์ง๋๋ค.
2 ์ด์์ n์ด ์ ๋ ฅ๋์์ ๋, n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ 1234567์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ๋ฆฌํดํ๋ ํจ์, solution์ ์์ฑํด ์ฃผ์ธ์.
n
์ 2์ด์ 100,000 ์ดํ์ธ ์์ฐ์์
๋๋ค.n | return |
---|---|
3 | 2 |
5 | 5 |
ํผ๋ณด๋์น์๋ 0๋ฒ์งธ๋ถํฐ 0, 1, 1, 2, 3, 5, ... ์ ๊ฐ์ด ์ด์ด์ง๋๋ค.
์ฐ์ , ํผ๋ณด๋์น ์์ด์ ๊ณต์ F(n) = F(n-1) + F(n-2)
๋ฅผ ํ์ฉํด ์ฌ๊ทํจ์๋ก ๊ตฌํ์ ํด๋ณด์๋ค.
class Solution {
public int fb(int n) {
if (n <= 2) {
return 1;
}
else {
return fb(n - 1) + fb(n - 2);
}
}
public int solution(int n) {
int answer = 0;
answer = fb(n) % 1234567;
return answer;
}
}
์ญ์๋ ์ซ์๊ฐ ์ปค์ง์ ๋ฐ๋ผ ์คํ ์๊ฐ์ด ๊ธฐํ๊ธ์์ ์ผ๋ก ๋์ด๋๋ฉด์, ์๊ฐ์ด๊ณผ๋ฅผ ์ผ๊ธฐํ๋ค.
์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ๋์ ๊ณํ๋ฒ(Dynamic Programming)์ ์ ์ฉํด๋ณด๊ธฐ๋ก ํ์๋ค.
class Solution {
public int solution(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n] % 1234567;
}
}
dp
๋ผ๋ ๋ฐฐ์ด์ ํ๋ ๋ง๋ค์ด, ์์์๋ถํฐ ๊ณ์ฐํ ๊ฐ๋ค์ ์ ์ฅํด๋๊ฐ๋ฉด, ์ค๋ณต๋๋ ๊ณ์ฐ์ ์ค์ผ ์๊ฐ ์๋ค.
์ด๋ฅผ ๋์ ํ๋ก๊ทธ๋๋ฐ์ ๊ธฐ๋ฒ ์ค Memoization์ด๋ผ๊ณ ํ๋ค.
๋์ ๊ณํ๋ฒ์ ์ฌ์ฉํ๋ ์๊ฐ ์ด๊ณผ๋ ํผํ ์ ์์์ง๋ง, ๋ช ๊ฐ์ ํ ์คํธ ์ผ์ด์ค์์ ์คํจ๊ฐ ๋ฐ์ํ์๋ค.
์๊ณ ๋ณด๋, n์ด ๋งค์ฐ ํฐ ๊ฒฝ์ฐ n๋ฒ์งธ ํผ๋ณด๋์น ์๊ฐ ์๋ฃํ์ ๋ฒ์๋ฅผ ๋์ด๊ฐ ์ ์๊ธฐ ๋๋ฌธ์ ์ค๋ฒํ๋ก์ฐ๊ฐ ๋ฐ์ํ ๊ฒ์ด๋ค.
์๋ฅผ ๋ค์ด, 47๋ฒ์งธ ํผ๋ณด๋์น ์๋ 2,971,215,073์ด๊ณ , ์ด ์๋ 32๋นํธ ์ ์(ex. int) ๋ฒ์๋ฅผ ๋์ด ์ค๋ฒํ๋ก์ฐ๊ฐ ๋ฐ์ํ๊ฒ ๋๋ค.
๋ฌธ์ ์กฐ๊ฑด์ ํผ๋ณด๋์น ์๋ฅผ 1234567
๋ก ๋๋ ๋๋จธ์ง๋ฅผ ๋ฐํํ๋ ๊ฒ์ธ๋ฐ, ์ต์ข
return๋ฌธ์์ 1234567
๋ก ๋๋ ์ฃผ๋ ๋์ , ํผ๋ณด๋์น ์๋ฅผ ๊ณ์ฐํ๊ณ dp
๋ฐฐ์ด์ ์ ์ฅํ ๋ ๋งค๋ฒ 1234567
๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ ์ฅํ๋๋ก ์์ ํด์ค์ผ๋ก์จ, ์ด๋ฅผ ํด๊ฒฐํ ์ ์์๋ค!
class Solution {
public int solution(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
}
return dp[n];
}
}
์ฐจ๊ทผ์ฐจ๊ทผ ๋ฌธ์ ํด๊ฒฐ...! ๋ฉ์์ด์