백준 #1038 감소하는 수

이 문제는 한참 백준 문제들을 풀 때 풀었던 문제네요.  그 당시에는 하루에 20여 문제도 풀곤 했었는데, 이제는 문제 수준도 어려워지고 생각도 많이 해야 해서 많이 못 풀고 있습니다.

 

감소하는 수라는 것은 31, 7543, 941 과 같이 숫자가 감소하는 방향으로만 이루어진 수입니다.  이런 숫자들을 크기순으로 나열했을 때, 정해진 순번의 숫자를 출력하면 됩니다.  문제를 잘 읽어보시다 보면 문제에 함정이 숨어 있습니다.  이 문제는 Gold IV 수준의 문제로 되어 있습니다.

 

문제의 링크는 다음과 같습니다.

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

1038번: 감소하는 수

이 문제의 함정을 알아챘다면, 실제 필요한 숫자의 갯수는 1022개라는 것을 알 수 있습니다.

 

감소하는 수의 총수는 10 개 중에 k 개를 구하는 경우의 수의 합입니다.

 

\[ \sum_{k=1}^{10} ~_{10}C_k \]

 

이러면 총 갯수가 1023개가 나옵니다.  조합의 합을 0부터 10까지 한다면 1024이겠지만, 일단 하나도 선택하지 않는 경우는 숫자가 되지 않습니다.  예를 들어서 4가 선택한 수가 0, 3, 7, 9 였다면, 이 숫자들 가지고 만들 수 있는 감소하는 수는 9730 이 유일하죠.  그래서 조합을 통해서 총 갯수를 알 수 있습니다.

 

이 문제를 정석대로 풀고 싶다면, 1개를 선택하는 경우의 수부터 차례대로 빼주면 됩니다.  총 경우의 수가 1022개인만큼 간단한 조합함수를 만들어도 결과가 오버플로우 날 위험이 없습니다.

 

전, 이 문제를 풀기위해서 속임수를 썼습니다.  애시당초 문제 낸 사람이 숫자 범위를 1,000,000까지 줌으로써 속였으니까요.  1023개의 숫자에 대한 것을 아예 배열에 저장해놓았습니다.  그래보았자 4KByte의 용량이니까요.

 

그래서 나온 소스는 다음과 같습니다.  소스는 참고용으로만 봐주세요.

//------------------------------------------------------------------------------
//  baekjoon #1038 - Decreasing Number
//  - by Aubrey Choi
//  - created at 2019-11-08
//------------------------------------------------------------------------------
#include <stdio.h>
/*
#include <algorithm>
bool cmp(int a, int b)
{
  int ac=0, bc=0;
  for(int i=0;i<10;i++) ac+=(a>>i)&1,bc+=(b>>i)&1;
  if(ac==bc) return a<b; return ac<bc;
}
void gen()
{
  int v[1023];
  for(int i=0;i<1023;i++) v[i]=i+1;
  std::sort(v,v+1023,cmp);
  for(int i=0;i<1023;i++) { printf("%d,", v[i]); if(i%16==15) putchar('\n'); }
}
*/

const int d[]= { 1,2,4,8,16,32,64,128,256,512,3,5,6,9,10,12,
  17,18,20,24,33,34,36,40,48,65,66,68,72,80,96,129,
  130,132,136,144,160,192,257,258,260,264,272,288,320,384,513,514,
  516,520,528,544,576,640,768,7,11,13,14,19,21,22,25,26,
  28,35,37,38,41,42,44,49,50,52,56,67,69,70,73,74,
  76,81,82,84,88,97,98,100,104,112,131,133,134,137,138,140,
  145,146,148,152,161,162,164,168,176,193,194,196,200,208,224,259,
  261,262,265,266,268,273,274,276,280,289,290,292,296,304,321,322,
  324,328,336,352,385,386,388,392,400,416,448,515,517,518,521,522,
  524,529,530,532,536,545,546,548,552,560,577,578,580,584,592,608,
  641,642,644,648,656,672,704,769,770,772,776,784,800,832,896,15,
  23,27,29,30,39,43,45,46,51,53,54,57,58,60,71,75,
  77,78,83,85,86,89,90,92,99,101,102,105,106,108,113,114,
  116,120,135,139,141,142,147,149,150,153,154,156,163,165,166,169,
  170,172,177,178,180,184,195,197,198,201,202,204,209,210,212,216,
  225,226,228,232,240,263,267,269,270,275,277,278,281,282,284,291,
  293,294,297,298,300,305,306,308,312,323,325,326,329,330,332,337,
  338,340,344,353,354,356,360,368,387,389,390,393,394,396,401,402,
  404,408,417,418,420,424,432,449,450,452,456,464,480,519,523,525,
  526,531,533,534,537,538,540,547,549,550,553,554,556,561,562,564,
  568,579,581,582,585,586,588,593,594,596,600,609,610,612,616,624,
  643,645,646,649,650,652,657,658,660,664,673,674,676,680,688,705,
  706,708,712,720,736,771,773,774,777,778,780,785,786,788,792,801,
  802,804,808,816,833,834,836,840,848,864,897,898,900,904,912,928,
  960,31,47,55,59,61,62,79,87,91,93,94,103,107,109,110,
  115,117,118,121,122,124,143,151,155,157,158,167,171,173,174,179,
  181,182,185,186,188,199,203,205,206,211,213,214,217,218,220,227,
  229,230,233,234,236,241,242,244,248,271,279,283,285,286,295,299,
  301,302,307,309,310,313,314,316,327,331,333,334,339,341,342,345,
  346,348,355,357,358,361,362,364,369,370,372,376,391,395,397,398,
  403,405,406,409,410,412,419,421,422,425,426,428,433,434,436,440,
  451,453,454,457,458,460,465,466,468,472,481,482,484,488,496,527,
  535,539,541,542,551,555,557,558,563,565,566,569,570,572,583,587,
  589,590,595,597,598,601,602,604,611,613,614,617,618,620,625,626,
  628,632,647,651,653,654,659,661,662,665,666,668,675,677,678,681,
  682,684,689,690,692,696,707,709,710,713,714,716,721,722,724,728,
  737,738,740,744,752,775,779,781,782,787,789,790,793,794,796,803,
  805,806,809,810,812,817,818,820,824,835,837,838,841,842,844,849,
  850,852,856,865,866,868,872,880,899,901,902,905,906,908,913,914,
  916,920,929,930,932,936,944,961,962,964,968,976,992,63,95,111,
  119,123,125,126,159,175,183,187,189,190,207,215,219,221,222,231,
  235,237,238,243,245,246,249,250,252,287,303,311,315,317,318,335,
  343,347,349,350,359,363,365,366,371,373,374,377,378,380,399,407,
  411,413,414,423,427,429,430,435,437,438,441,442,444,455,459,461,
  462,467,469,470,473,474,476,483,485,486,489,490,492,497,498,500,
  504,543,559,567,571,573,574,591,599,603,605,606,615,619,621,622,
  627,629,630,633,634,636,655,663,667,669,670,679,683,685,686,691,
  693,694,697,698,700,711,715,717,718,723,725,726,729,730,732,739,
  741,742,745,746,748,753,754,756,760,783,791,795,797,798,807,811,
  813,814,819,821,822,825,826,828,839,843,845,846,851,853,854,857,
  858,860,867,869,870,873,874,876,881,882,884,888,903,907,909,910,
  915,917,918,921,922,924,931,933,934,937,938,940,945,946,948,952,
  963,965,966,969,970,972,977,978,980,984,993,994,996,1000,1008,127,
  191,223,239,247,251,253,254,319,351,367,375,379,381,382,415,431,
  439,443,445,446,463,471,475,477,478,487,491,493,494,499,501,502,
  505,506,508,575,607,623,631,635,637,638,671,687,695,699,701,702,
  719,727,731,733,734,743,747,749,750,755,757,758,761,762,764,799,
  815,823,827,829,830,847,855,859,861,862,871,875,877,878,883,885,
  886,889,890,892,911,919,923,925,926,935,939,941,942,947,949,950,
  953,954,956,967,971,973,974,979,981,982,985,986,988,995,997,998,
  1001,1002,1004,1009,1010,1012,1016,255,383,447,479,495,503,507,509,510,
  639,703,735,751,759,763,765,766,831,863,879,887,891,893,894,927,
  943,951,955,957,958,975,983,987,989,990,999,1003,1005,1006,1011,1013,
  1014,1017,1018,1020,511,767,895,959,991,1007,1015,1019,1021,1022,1023 };
int main()
{
  int n;
  scanf("%d",&n);
  if(n>=1023) { puts("-1"); return 0; }
  for(int i=9;i>=0;i--) if((d[n]>>i)&1) putchar(i+'0'); putchar('\n');
}