<aside> 1️⃣

문제 설명: 1003번 피보나치 함수

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번 출력

fibonacci(N) 호출 시 0과 1이 각각 몇 번 출력되는지 구하기

</aside>

<aside> ✅

코드

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);

		//동적 프로그래밍 사용
    int dp[41][2]; // dp[n][0]: 0 출력 횟수, dp[n][1]: 1 출력 횟수

    // 기본값 설정
    dp[0][0] = 1; dp[0][1] = 0;
    dp[1][0] = 0; dp[1][1] = 1;
    // DP 테이블 채우기
    for (int i = 2; i <= 40; i++) {
		    // fibonacci(i)를 호출할 때 출력되는 0의 횟수는
		    // fibonacci(i-1)을 호출할 때 출력된 0의 횟수 + fibonacci(i-2)를 호출할 때 출력된 0의 횟수
        dp[i][0] = dp[i-1][0] + dp[i-2][0];
        dp[i][1] = dp[i-1][1] + dp[i-2][1];
    }

    for (int i = 0; i < T; i++) {
        int N;
        scanf("%d", &N);
        printf("%d %d\\n", dp[N][0], dp[N][1]);
    }
}

</aside>

<aside> 2️⃣

문제 설명: 1463번 1로 만들기

아래 연산을 사용해 정수 N을 1로 만들 때 연산을 사용하는 횟수의 최솟값 구하기

1. X가 3으로 나누어 떨어지면 3으로 나눔
2. X가 2로 나누어 떨어지면 2로 나눔
3. 1을 뺌 </aside>

<aside> ✅

코드

#include <stdio.h>

int dp[1000001];

int main() {
	int N;
	scanf("%d", &N);

//동적 프로그래밍 사용
	dp[1] = 0; //1인 경우 연산 X
	for (int i = 2; i <= N; i++) {
		//i를 만들기 위한 최소 연산 횟수는 i-1값 +1
		//1을 빼는 연산만 한 것을 가정한 값
		dp[i] = dp[i - 1] + 1; 
		
		//2로 나누어 떨어질 때 앞의 값과 비교하여 더 작은 값으로 갱신
		if (i % 2 == 0) dp[i] = dp[i] < dp[i / 2] + 1 ? dp[i] : dp[i / 2] + 1;
		//3으로 나누어 떨어지는 경우 동일하게
		if (i % 3 == 0) dp[i] = dp[i] < dp[i / 3] + 1 ? dp[i] : dp[i / 3] + 1;
	}

	printf("%d", dp[N]);
}

• 처음엔 그리디 알고리즘으로 작성해 오답

</aside>