๋ฌธ์
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ํผ๋ณด๋์น ์
ํผ๋ณด๋์น ์๋ F(0) = 0, F(1) = 1์ผ ๋, 1 ์ด์์ n์ ๋ํ์ฌ F(n) = F(n-1) + F(n-2) ๊ฐ ์ ์ฉ๋๋ ์ ์ ๋๋ค. ์๋ฅผ๋ค์ด F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) =
programmers.co.kr
์ฝ๋
#include <string>
#include <vector>
#define MOD 1234567
using namespace std;
int dp[100001];
int solution(int n) {
int answer = 0;
dp[0]=0;
dp[1]=1;
for(int i=2; i<=n; i++){
dp[i]=(dp[i-1]%MOD+dp[i-2]%MOD)%MOD;
}
answer=dp[n];
return answer;
}
ํ์ด
bottom - up ๋ฐฉ์์ ๋จ์ํ dynamic-programming ๋ฌธ์ ์์ต๋๋ค.
'Algorithm ๐ง๐ปโ๐ป > ํ๋ก๊ทธ๋๋จธ์ค(Programmers)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[c++] ํ๋ก๊ทธ๋๋จธ์ค - ํผ๋ก๋(Level 2) (0) | 2022.03.04 |
---|---|
[c++] ํ๋ก๊ทธ๋๋จธ์ค - ์์ด ๋๋ง์๊ธฐ(Level 2) (0) | 2022.03.04 |
[c++] ํ๋ก๊ทธ๋๋จธ์ค - ์ฝ์์ ๊ฐ์์ ๋ง์ (Level 1) (0) | 2022.02.13 |
[c++] ํ๋ก๊ทธ๋๋จธ์ค - ์ต๋๊ณต์ฝ์์ ์ต์๊ณต๋ฐฐ์( Level1) (0) | 2021.11.08 |
[c++] ํ๋ก๊ทธ๋๋จธ์ค - ๋ฐฐ๋ฌ( Level2) (0) | 2021.11.08 |
[c++] ํ๋ก๊ทธ๋๋จธ์ค - ์ ์ผ ์์ ์ ์ ๊ฑฐํ๊ธฐ( Level1) (0) | 2021.11.08 |
๋๊ธ