[백준 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;
}