[๋ฐฑ์ค€ 1003] ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜ (C++)

2023. 10. 25. 16:50ยท๐Ÿ–ฅ๏ธ Study Note/Coding Test

https://www.acmicpc.net/problem/1003

๋ฌธ์ œ

๋‹ค์Œ ์†Œ์Šค๋Š” N๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” C++ ํ•จ์ˆ˜์ด๋‹ค.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(nโ€1) + fibonacci(nโ€2);
    }
}

fibonacci(3)์„ ํ˜ธ์ถœํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ผ์ด ์ผ์–ด๋‚œ๋‹ค.

  • fibonacci(3)์€ fibonacci(2)์™€ fibonacci(1) (์ฒซ ๋ฒˆ์งธ ํ˜ธ์ถœ)์„ ํ˜ธ์ถœํ•œ๋‹ค.
  • fibonacci(2)๋Š” fibonacci(1) (๋‘ ๋ฒˆ์งธ ํ˜ธ์ถœ)๊ณผ fibonacci(0)์„ ํ˜ธ์ถœํ•œ๋‹ค.
  • ๋‘ ๋ฒˆ์งธ ํ˜ธ์ถœํ•œ fibonacci(1)์€ 1์„ ์ถœ๋ ฅํ•˜๊ณ  1์„ ๋ฆฌํ„ดํ•œ๋‹ค.
  • fibonacci(0)์€ 0์„ ์ถœ๋ ฅํ•˜๊ณ , 0์„ ๋ฆฌํ„ดํ•œ๋‹ค.
  • fibonacci(2)๋Š” fibonacci(1)๊ณผ fibonacci(0)์˜ ๊ฒฐ๊ณผ๋ฅผ ์–ป๊ณ , 1์„ ๋ฆฌํ„ดํ•œ๋‹ค.
  • ์ฒซ ๋ฒˆ์งธ ํ˜ธ์ถœํ•œ fibonacci(1)์€ 1์„ ์ถœ๋ ฅํ•˜๊ณ , 1์„ ๋ฆฌํ„ดํ•œ๋‹ค.
  • fibonacci(3)์€ fibonacci(2)์™€ fibonacci(1)์˜ ๊ฒฐ๊ณผ๋ฅผ ์–ป๊ณ , 2๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค.

1์€ 2๋ฒˆ ์ถœ๋ ฅ๋˜๊ณ , 0์€ 1๋ฒˆ ์ถœ๋ ฅ๋œ๋‹ค. N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, fibonacci(N)์„ ํ˜ธ์ถœํ–ˆ์„ ๋•Œ, 0๊ณผ 1์ด ๊ฐ๊ฐ ๋ช‡ ๋ฒˆ ์ถœ๋ ฅ๋˜๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 40๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜ ๋˜๋Š” 0์ด๋‹ค.

์ถœ๋ ฅ

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜์™€ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜๋ฅผ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ์ถœ๋ ฅํ•œ๋‹ค.

๋‚ด ํ’€์ด

dp๋กœ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๋ผ dp๋ฅผ ํ™œ์šฉํ•˜์—ฌ ํ’€์–ด์ฃผ์—ˆ๋‹ค.

N์ด ์ตœ๋Œ€ 40์ด๊ธฐ ๋•Œ๋ฌธ์— ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•ด๋„ ๋ถ€๋‹ด์ด ์—†์–ด ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•œ ๋’ค์—,

์ž…๋ ฅํ•œ ๊ฐ’์— ๋”ฐ๋ฅธ ๊ณ„์‚ฐ ๊ฒฐ๊ณผ ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•ด์ฃผ์—ˆ๋‹ค.

#include <iostream>
using namespace std;

int main()
{
	long long dp[41][2];
	dp[0][0] = 1;
	dp[0][1] = 0;
	dp[1][0] = 0;
	dp[1][1] = 1;

	for (int i = 0; i < 41; ++i)
	{
		if (i >= 2)
		{
			dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
			dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
		}
	}

	int count;
	cin >> count;
	int n;
	for (int i = 0; i < count; ++i)
	{
		cin >> n; 
		cout << dp[n][0] << ' ' << dp[n][1] << endl;
	}

}
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'๐Ÿ–ฅ๏ธ Study Note > Coding Test' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€ 1926] ๊ทธ๋ฆผ(C++)  (0) 2023.11.18
[๋ฐฑ์ค€ 1931] ํšŒ์˜์‹ค ๋ฐฐ์ •(C++)  (0) 2023.10.26
[Hacker Rank] Organizing Containers of Balls (C++)  (1) 2023.10.09
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.3 - ์นด๋“œ ์ง ๋งž์ถ”๊ธฐ(C++)  (1) 2023.10.05
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.3 - ๋ถ€๋Œ€๋ณต๊ท€ (C++)  (0) 2023.10.04
'๐Ÿ–ฅ๏ธ Study Note/Coding Test' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€ 1926] ๊ทธ๋ฆผ(C++)
  • [๋ฐฑ์ค€ 1931] ํšŒ์˜์‹ค ๋ฐฐ์ •(C++)
  • [Hacker Rank] Organizing Containers of Balls (C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.3 - ์นด๋“œ ์ง ๋งž์ถ”๊ธฐ(C++)
Beankong_
Beankong_
์ฃผ๋‹ˆ์–ด ํด๋ผ์ด์–ธํŠธ ํ”„๋กœ๊ทธ๋ž˜๋จธ ๊ณต๋ถ€ ๊ธฐ๋ก
  • Beankong_
    Beankong's Devlog
    Beankong_
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ์ „์ฒด ๊ธ€ (146)
      • โ›… Daily (0)
      • ๐Ÿ–ฅ๏ธ Study Note (2)
        • C++ (1)
        • Unreal Engine (5)
        • Coding Test (123)
        • Design Patteren (5)
        • VCS (Git..) (1)
        • Server (1)
      • ๐Ÿงญ Devlog (8)
        • ์˜ค๋‹ต๋…ธํŠธ (4)
        • UE5 GameLift Server Test Project (1)
        • TIL (3)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ๋งํฌ

    • ๊ณต์ง€์‚ฌํ•ญ

    • ์ธ๊ธฐ ๊ธ€

    • ํƒœ๊ทธ

      programmers
      ํ—ฌํ…Œ์ด์ปค
      cpp
      ์•Œ๊ณ ๋ฆฌ์ฆ˜
      ๊ฒŒ์ž„ ๋ชจ์ž‘
      ํ”„๋ฃŒ๊ทธ๋ž˜๋จธ์Šค
      OnlineSubsystem
      ๊ฒŒ์ž„ํ”„๋กœ๊ทธ๋ž˜๋ฐ
      UnrealEngine5
      UnrealEngine
      ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜
      ๊ฒŒ์ž„ ํ”„๋กœ๊ทธ๋ž˜๋ฐ
      ๊ฒŒ์ž„ ๊ฐœ๋ฐœ
      ์ฝ”๋”ฉํ…Œ์ŠคํŠธ
      unrealengine module
      propertyaccess
      unrealengine build system
      ๊ทธ๋ฆฌ๋””(greedy)
      ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
      ๊ทธ๋ž˜ํ”„ ์ˆœํšŒ
    • ์ตœ๊ทผ ๋Œ“๊ธ€

    • ์ตœ๊ทผ ๊ธ€

    • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
    Beankong_
    [๋ฐฑ์ค€ 1003] ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜ (C++)
    ์ƒ๋‹จ์œผ๋กœ

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”