C++ 공부 15일차 (11723, 1003, 1463, 17626, 2579)

오늘 공부한 백준

11723, 1003, 1463, 17626, 2579

 

다이내믹 프로그래밍

과거에 구한 해를 활용하는 알고리즘

구하는 경로가 고정되어 있는 해를 구할 때 유용

 

 

1003 (피보나치 함수)

int fibonacci(int n) {
    dp[n][0] = dp[n-1][0]+dp[n-2][0];
    dp[n][1] = dp[n-1][1]+dp[n-2][1];
	    
    return 0;
}

 

1463 (1 만들기)

    //미리 만들어 놓는다
    dp[1] = 0;
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + 1;
        if(i % 2 == 0) dp[i] = min(dp[i / 2] + 1, dp[i]);
        if(i % 3 == 0) dp[i] = min(dp[i / 3] + 1, dp[i]);
    }

 

17626 (FOUR SQUARES)

    for(int i = 2; i <= n; i++){
        cnt[i] = cnt[i - 1] + 1;
        for(int j = 1; j*j <= i; j++){
            cnt[i] = min(cnt[i], cnt[i - j*j] + 1);
        }
    }

 

2579 (계단 오르기)

    //계단의 합
    int sum[MAXN];

    sum[0] = curr[0];
    sum[1] = curr[0] + curr[1];
    sum[2] = max(curr[1] + curr[2], curr[0] + curr[2]);
    for(int i = 3; i < n; i++){
        sum[i] = sum[i - 3] + curr[i - 1] + curr[i];
        sum[i] = max(sum[i], sum[i - 2] + curr[i]);
    }