scpc 2019 예선 1차 1번 문제 : 오르락 내리락 - Junnnho

1번 문제는 BOJ 1로 만들기 와 비슷하다 https://www.acmicpc.net/problem/1463

한창 DP 기본문제들 풀 때 풀었던 문제였는데

1번 문제를 보고 어디서 많이 본 느낌이 났었다.

 

#include <iostream>
using namespace std;
 
int dp[1000001];
int sum[1000001];
 
int main() {
    int T, num, num2;
    int Answer = 0;
    cin >> T;
 
 
    dp[1] = 0, dp[2] = 1, dp[3] = 3, dp[4] = 2, dp[5] = 5, dp[6] = 4;
 
    for (int i = 5; i < 1000001; i++) {
        if (i % 2 == 0) {
            dp[i] = dp[i / 2] + 1;
        }
        else if (i % 2 == 1) {
            dp[i] = dp[i / 2 + 1] + 2;
        }
    }
 
    for (int i = 1; i < 1000001; i++) {
        sum[i] += dp[i] + sum[i - 1];
    }
 
    for (int i = 1; i <= T; i++) {
        
        cin >> num >> num2;
 
        cout << "Case #" << i << '\n' << sum[num2] - sum[num - 1] << '\n';
    }
 
    return 0;
}