_ 2410 - 2의 멱수의 합

문제 링크

처음 짰던 코드이다.
case 분류를 크게 홀수, 짝수 와 짝수인 경우 2가지로 나눴다.
2의 멱수인 경우와 그냥 짝수인 경우.

#include <iostream>
using namespace std;

int save[1000001];
const int DIV = 1000000000;
bool isPowerOfTwo(int num);

int main() {
    int input;
    cin >> input;
    
    //Initialize
    save[1] = 1;
    save[2] = 2;
    
    if (input < 3) {
        cout << save[input];
        return 0;
    }
    
    for(int i = 3; i<= input; i++) {
        if (i % 2 == 1) {
            save[i] = save[i-1] % DIV; 
        } else {
            if (isPowerOfTwo(i)) {
                save[i] = (save[i-1] + save[i-2]- save[i-3] + 1) % 1000000000;
            } else {
                save[i] = (save[i-1] + save[i-2] - save[i-3]) % 1000000000;
            }
        }
    }
    
    cout << save[input];
    
    return 0;
}

bool isPowerOfTwo(int num) {
    int n = num;
    while ( n > 1 ) {
        if (n % 2 == 1) {
            return false;
        } else {
            n = n / 2;
        }
    }
    return true;
}

결과는 ?

흠. 점화식을 잘못짰다.
2의 멱수인 경우.

save[i] = (save[i-1] + save[i-2]- save[i-3] + 1) % DIV;

그렇지 않은 짝수인 경우.

save[i] = (save[i-1] + save[i-2]- save[i-3]) % DIV;

이게 의심스럽다.

제대로된 풀이

        if (i % 2 == 1) {
            save[i] = save[i-1] % DIV; 
        } else {
            save[i] = (save[i-1] + save[i/2]) % DIV;
        }

이렇게 고치면 된다!

그럼 골드찍을 그날까지...👻