[C++] 백준 3687 성냥개비

#include <iostream>
#include <vector>
 
int arr[9] = { 0, 0, 1, 7, 4, 2, 0, 8, 10 };
 
long long DP[101] = {};
 
int main()
{
    int N = 0;
 
    std::cin >> N;
 
    for (int i = 1; i < 9; ++i)
    {
        DP[i] = arr[i];
    }
 
    DP[6] = 6;
 
    for (int i = 9; i < 101; ++i)
    {
        DP[i] = DP[i - 2] * 10 + arr[2];
 
        for (int j = 3; j < 8; ++j)
        {
            DP[i] = std::min(DP[i], DP[i - j] * 10 + arr[j]);
        }
    }
 
    for (int i = 0; i < N; ++i)
    {
        int iNumber = 0;
        std::cin >> iNumber;
 
        std::cout << DP[iNumber] << " ";
 
        while (iNumber)
        {
            if (iNumber % 2 != 0)
            {
                std::cout << 7;
                iNumber -= 3;
            }
 
            else 
            {
                std::cout << 1;
                iNumber -= 2;
            }
        }
 
        std::cout << "\n";
    }
 
    return 0;
}

최솟값 구하기 위해서 좀 헷갈렸다.

처음에는 7을 빼고 나머지를 구했는데 200일 때랑 688일 때의 갯수가 같아서 문제가 되었다...

자꾸 손으로 풀려는 경향이 있는데... DP나 이분 탐색을 좀 잘 이용할 수 있어야 할 것 같다.