반응형

문제

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


다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1
2
3
4
5
6
7
8
9
10
11
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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.


입력

3
0
1
3

출력

1 0
0 1
1 2


fibonacci(n) 이하 fi(n)은 피보나치 함수이다.

fi(0)과 fi(1)은 각각 0과 1을 반환하며 fi(2)는 fi(1)+fi(0)임을 알 수 있다.

이때 fi(1)은 1이 출력되는 횟수 fi(0)은 0이 출력되는 횟수로 접근하면 된다.


fi(2) = fi(1) + fi(0)

fi(3) = fi(2) + fi(1) = fi(1) + fi(0) + fi(1)

fi(4) = fi(3) + fi(2) =  fi(1) + fi(0) + fi(1) + fi(1) + fi(0) 

==> fi(1) + fi(0) + fi(1) + fi(1) + fi(0) 

fi(5) = fi(4) + fi(3) = fi(1) + fi(0) + fi(1) + fi(1) + fi(0) + fi(1) + fi(0) + fi(1)

==> fi(1) + fi(0) + fi(1) + fi(1) + fi(0) + fi(1) + fi(0) + fi(1)


 

 0 횟수

1 횟수 

 fi(2)

1 

1 

 fi(3)

1 

2 

 fi(4)

2 

3 

 fi(5)

3

5 


표를 보면 더 쉽게 규칙을 찾을 수 있다

즉 fi(4) 에서 0과 1의 횟수는 fi(2)의 횟수 + fi(3)의 횟수 이며 

fi(5)도 fi(4)의 횟수 + fi(3)의 횟수이다.

따라서 fi(n) = fi(n-1) + fi(n-2) 라는 점화식을 뽑아낼 수 있다.


소스

//

//  main.cpp

//  DP

//

//  Created by seungwoo on 2018. 06. 28

//  Copyright © 2018년 seungwoo. All rights reserved.

//


#include <iostream>

#include <algorithm>


using namespace std;


void fibo(int n);

void init();

int dp[2][41] = {0};

int main()

{

int T,n; // 0<=n<=40

cin>>T;

init();

while(T>0){

T--;

cin>>n;

fibo(n);

cout<<dp[0][n]<<" "<<dp[1][n]<<endl;

}

return 0;

}

void fibo(int n)

{

for(int i=2;i<=n;i++){

dp[0][i] = dp[0][i-1] + dp[0][i-2];

dp[1][i] = dp[1][i-1] + dp[1][i-2];

}

}

void init()

{

dp[0][0] = 1;

dp[0][1] = 0;

dp[1][0] = 0;

dp[1][1] = 1;

}


이와 같이 2차원 배열을 이용하여 쉽게 프로그램을 구현할 수 있다.

dp로 풀이하지 않아도 쉬운 문제이나 dp로 풀지 않은 소스와 dp로 푼 소스는 실행시간에 큰 차이를 보인다.

반응형

'Algorithm' 카테고리의 다른 글

[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1932] 숫자삼각형  (0) 2018.03.30
[백준 1149] RGB거리  (0) 2018.03.29
[백준 9095] 1,2,3 더하기  (0) 2018.03.27
반응형

문제

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


문제 설명

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

예제 입력

3
4
7
10

예제 출력

7
44
274



1을 만드는 방법 =  1가지

(1)

2를 만드는 방법 = 2가지

(1+1) / (2)

3을 만드는 방법 = 4가지

(1+1+1) / (1+2) / (2+1) / (3)

4를 만드는 방법 = 7가지

(1+1+1+1) / (1+1+2) / (1+2+1) / (1+3) / (2+1+1) / (2+2) / (3+1)

5를 만드는 방법 = 12가지

.....


3을 만드는 방법에서 예를 들면

1+1+1 에서 가장 앞 부분인 1을 제외하면

2를 만드는 방법의 가지수를 구해주면 2가지 이다.


이후 가장 먼저 2를 더할 때는 3-2의 값인 1을 만드는 경우의 수

3을 가장 먼저 더할때는 3을 만들 수 있는 경우의 수를 구하는 방식이다.


즉

dp[3] = 4 인 것을 구했다면

dp[4] 를 유추해 보자


dp[4] = 1 + dp[3]

  + 2 + dp[2]

  + 3 + dp[1]

임을 알 수 있으며 이는 4 + 2 + 1 = 7가지의 방법으로 4를 만들 수 있다.


이 점화식을 일반화 시키면 dp[n] = dp[n-1]+ dp[n-2] + dp[n-3] 이므로 이후 소스 작성은 어렵지 않을 것이다.


소스


//

//  main.cpp

//  DP

//

//  Created by seungwoo on 2018. 3. 27..

//  Copyright © 2018년 seungwoo. All rights reserved.

//


#include <iostream>

#include <algorithm>


using namespace std;


int main(int argc, const char * argv[]) {

    

    int testcase,n;

    int dp[11]; //N<11

    cin>>testcase;

    

    // f(n) = f(n-1) + f(n-2) + f(n-3)

    dp[1] = 1;

    dp[2] = 2;

    dp[3] = 4;

    for(int i = 0; i<testcase; i++){

        cin>>n; //정수 n

        for(int j=4;j<=n;j++){

            dp[j] = dp[j-1] + dp[j-2] + dp[j-3];

        }

        cout<<dp[n]<<endl;

    }

    return 0;

} 





반응형

'Algorithm' 카테고리의 다른 글

[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1932] 숫자삼각형  (0) 2018.03.30
[백준 1149] RGB거리  (0) 2018.03.29
[백준 1003] 피보나치 함수  (0) 2018.03.28

+ Recent posts

티스토리툴바