백준 2410번 2의 멱수의 합

문제 링크입니다: https://www.acmicpc.net/problem/2410

2의 n 제곱수의 합으로 표현할 수 있는 방법의 수를 쉽게 구하기 위해 cmath 헤더파일의 pow 함수를 사용했던 문제였습니다.

DP를 적용하기 위해 cache[MAX][20] 이차원 배열을 선언했는데 pow(2, 20) = 1,048,576이기 때문에 20으로 했습니다.

처음에는 cache[MAX][MAX]로 선언하려고 했지만 배열의 크기가 너무 크기 때문에 2^k를 표현하는 k승만 저장했습니다.

간단한 DP 문제였기 때문에 별도로 설명할 내용은 별로 없는 것 같고 조건충족에서 (num > 0 && k == 0)은 1을 통해 모든 숫자를 표현가능하기 때문에 2^k = 2^0 = 1의 경우 조건 충족 처리를  했습니다.

#include <iostream>

#include <cmath>

#include <cstring> //memset

using namespace std;

 

const int MOD = 1000000000;

const int MAX = 1000000 + 1;

 

int N;

int cache[MAX][20]; //현재 숫자, 2^20=1,048,576

 

int numOfWays(int num, int k)

{

        //기저 사례

        if (num < 0)

                 return 0;

        //조건 충족

        if (num == 0 || (num > 0 && k == 0))

                 return 1;

 

        int &result = cache[num][k];

        if (result != -1)

                 return result;

         

   //2^k을 사용 안한 경우와 사용한 경우

        result = (numOfWays(num, k - 1) % MOD + numOfWays(num - pow(2, k), k) % MOD) % MOD;

        return result;

}

 

int main(void)

{

        cin >> N;

 

        memset(cache, -1, sizeof(cache));

        cout << numOfWays(N, 19) % MOD << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~