[백준 2839번] 설탕 배달

문제 링크: 2839번 설탕 배달

https://www.acmicpc.net/problem/2839

 

큰 것부터 하되 하나씩 줄여나간다는 생각으로.

이게 봉지의 종류가 여러 가지가 된다면 배열에 담아야 할 것 같다.

그 땐 굉장히 복잡해질 건데, 어떻게 해야 할까...? 고민해보고 한 번 풀어보자.

 

#include <iostream>
#include <string>

using namespace std;

int main(void) {
    int i;

    bool arr[10000];    // arr[i] is true
                        // if n exists, false if n doesn't exist (n is gen. of d(n))

    for (i = 0; i < 10000; i++) {
        arr[i] = false;
    }

    for (int n = 1; n < 10000; n++) {
        string nStr = to_string(n);

        int sum = n;
        for (i = 0; i < nStr.size(); i++)
            sum += (nStr[i] - '0');
        if (sum > 10000)
            continue;

        arr[sum] = true;
    }

    for (i = 1; i < 10000; i++) {
        if (!arr[i])
            cout << i << '\n';
    }

    return 0;
}