끄적끄적 코딩
article thumbnail

 

 

다이나믹 프로그래밍 문제입니다.

 

위의 피보나치 함수를 실행할때 fibonacci(0)과 fibonacci(1)이 각각 몇번 실행되는지 구하는 문제입니다.

0이면 0을 리턴해주므로

0 = (1 0)

1이면 1을 리턴해주므로

1 = (0 1)

2면 2-1, 2-2를 실행시키므로

2 = (1 0) + (0 1)

2 = (1 1)이 됩니다.

3도 마찬가지로 3-1, 3-2를 실행시키는 방식으로 구할 수 있습니다.

 

memo[50][2]를 선언하였고 앞배열은 숫자 뒤에 배열은 0과 1의 개수를 넣었습니다.

memo[i][0] = memo[i-1][0] + memo[i-2][0]; // 0의 개수를 구함

memo[i][1] = memo[i-1][1] + memo[i-2][1]; // 1의 개수를 구함

위의 코드를 찾는 숫자까지 반복하여서 문제를 해결하였습니다.

 

#include <iostream>
using namespace std;

int memo[50][2];

void init()
{
   for (int i = 0; i < 50; ++i) {
      for (int j = 0; j < 50; ++j) {
         memo[i][j] = -1;
      }
   }
   memo[0][0] = 1;
   memo[0][1] = 0;
   memo[1][0] = 0;
   memo[1][1] = 1;
}

int main(int argc, char *argv[])
{
   init();
   int n;
   cin >> n;

   for (int i = 0; i < n; ++i) {
      int num;
      cin >> num;
      if (memo[num][0] != -1) {
         cout << memo[num][0] << " ";
         cout << memo[num][1] << endl;
         continue;
      }
      for (int j = 2; j <= num; ++j) {
         if (memo[j][0] != -1) {
            continue;
         }
         memo[j][0] = memo[j - 1][0] + memo[j - 2][0];
         memo[j][1] = memo[j - 1][1] + memo[j - 2][1];
      }
      cout << memo[num][0] << " ";
      cout << memo[num][1] << " " << endl;
   }
   return 0;
}

'알고리즘' 카테고리의 다른 글

[C++] 백준 1912번 연속합  (0) 2019.05.17
[C++] 백준 2156번 포도주 시식  (0) 2019.05.17
[C++] 백준 1932번 정수 삼각형  (0) 2019.05.17
[C++] 백준 2193번 이친수  (0) 2019.05.17
[C++] 백준 1149번 RGB거리  (0) 2019.05.09

검색 태그