-
[๋ฐฑ์ค(BOJ)] 10870๋ฒ ํผ๋ณด๋์น ์ 5, C์ธ์ด ํ์ดPS(Problem Solving)/C 2020. 7. 22. 11:31๋ฐ์ํ
<ํผ๋ณด๋์น ์ 5>, 10870๋ฒ
๋ฌธ์
ํผ๋ณด๋์น ์๋ 0๊ณผ 1๋ก ์์ํ๋ค. 0๋ฒ์งธ ํผ๋ณด๋์น ์๋ 0์ด๊ณ , 1๋ฒ์งธ ํผ๋ณด๋์น ์๋ 1์ด๋ค. ๊ทธ ๋ค์ 2๋ฒ์งธ ๋ถํฐ๋ ๋ฐ๋ก ์ ๋ ํผ๋ณด๋์น ์์ ํฉ์ด ๋๋ค.
์ด๋ฅผ ์์ผ๋ก ์จ๋ณด๋ฉด Fn = Fn-1 + Fn-2 (n>=2)๊ฐ ๋๋ค.
n=17์ผ๋ ๊น์ง ํผ๋ณด๋์น ์๋ฅผ ์จ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n์ด ์ฃผ์ด์ก์ ๋, n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ n์ด ์ฃผ์ด์ง๋ค. n์ 20๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์ ๋๋ 0์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1 ๋ณต์ฌ
10
์์ ์ถ๋ ฅ 1 ๋ณต์ฌ
55
ํ์ด
์ด ๋ฌธ์ ๋ ํผ๋ณด๋์น ์์ด์ ์ดํดํ๋ฉด ์ฝ๊ฒ ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ๋๋ ํผ๋ณด๋์น ์์ด์ ์ฒซ ๋ฒ์งธ ๊ฐ์ 0, ๋ ๋ฒ์งธ ๊ฐ์ด 1์ธ ๊ฒ์ ๊ฐ๊ฐ ๋ณ์ a, b์ ์ ์ฅํ๋ค. ์ด๋ฒ์๋ ์ฌ๊ท ํจ์๋ฅผ ์ฌ์ฉํด์ ์ด๋ฅผ ํ์ดํ๋ ค๊ณ ํ๊ธฐ ๋๋ฌธ์ if๋ฌธ์ ์ด์ฉํด์ ํผ๋ณด๋์น ์์ด์ ์ฒซ ๋ฒ์งธ์ ๋ ๋ฒ์งธ ๊ฐ์ด ์ ํด์ ธ ์๊ธฐ ๋๋ฌธ์ ์ด๋ฅผ return ํ๋๋ก ์ค์ ํ ํ ์ฌ๊ท์ ์ผ๋ก ํ์ดํด ๋๊ฐ ์ ์์๋ค.
#include <stdio.h> int Febo(int num) { int a, b; int c; int i; a = 0; b = 1; if (num == 0) return a; else if (num == 1) return b; else return Febo(num - 1) + Febo(num - 2); } int main(void) { int num; scanf_s("%d", &num); printf("%d", Febo(num)); return 0; }
๋ฐ์ํ