์ฝ๋ ๋ฐ๋ก๊ฐ๊ธฐ
๋ฌธ์ ํ์ธ
ํ์ด
๋ฌธ์ ํด์ค
์์ ์ ์ n์ ๋ํด d(n) = n + (n์ ๊ฐ ์๋ฆฌ์)
๊ฐ๋ น d(75) = 75 + 7 + 5 = 87
33์ผ๋ก ์์ํ๋ค๋ฉด ๋ค์ ์๋ 33+3+3=39,
๋ค์ ์๋ 39+3+9=51,
๋ค์ ์๋ 51+5+1=57์ด๋ค.
์ด๋ฅผ ์ด์ฉํ์ฌ {33, 39, 51, 57, โฆ} ์ ์์ด์ ๋ง๋ค ์ ์๋ค.
n์ d(n)์ ์์ฑ์์ด๋ค. 33์ 39์ ์์ฑ์์ด๋ค.
101์ 91(91+9+1=101)๊ณผ 100(100+1+0+0)์ผ๋ก 2๊ฐ์ ์์ฑ์๊ฐ ์๋ค.
์ด๋ ์
ํ ๋๋ฒ๋ โ์์ฑ์๊ฐ ์๋ ์โ๋ฅผ ์๋ฏธํ๋ค.
100๋ณด๋ค ์์ ์
ํ ๋๋ฒ๋ 1, 3, 5, 7, 9, 20, 31, โฆ ๋ก ์ด 13๊ฐ๊ฐ ์๋ค.
10000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์
ํ ๋๋ฒ๋ฅผ ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ์์ค.
์๊ณ ๋ฆฌ์ฆ
์์ฑ์๊ฐ ์๋ค = d(n)์ ๊ท์น์ผ๋ก ์์ฑ๋์ง ์๋ ์ (N์ 10,000)
1๋ถํฐ N๊น์ง d(n)์ ๊ท์น์ ์ ์ฉํ์ ๋ ๋ฑ์ฅํ ์๋ boolean ๋ฐฐ์ด์์ true๋ก ์ฒดํฌํด์ค๋ค. => O(N)
๋จ, ๊ฐ์ฅ ํฐ ์๋ 9999+9+9+9+9=10035์ด๋ boolean์ check[10036]
์ดํ 1๋ถํฐ N๊น์ง boolean ๋ฐฐ์ด์ ๋๋ฉฐ false์ธ ๊ฒฝ์ฐ ์ถ๋ ฅ => O(N)
์ด O(N+N) = O(N)
์ผ๋ก ๋ต์ ๊ตฌํ๊ณ , ์๊ฐ ์ ํ์ 1์ด์ด๋ฏ๋ก N์ด 10^8=100,000,000์ผ ๋ ๊น์ง๋ ๋ฌํํ๊ฒ ์ปค๋ฒ ๊ฐ๋ฅํฉ๋๋ค. ์ด๋ ๋ฌธ์ ์ ์ฃผ์ด์ง N์ 10,000์ด๋ฏ๋ก ์๊ฐ ๋ด์ ์ถฉ๋ถํ ๊ฐ๋ฅํฉ๋๋ค.
์ฝ๋
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <math.h>
using namespace std;
int makeNum(int n) {
int sum = n;
int tmp = n;
while (tmp >= 1) {
sum += tmp % 10;
tmp = floor(tmp / 10);
}
return sum;
}
int main()
{
bool check[10036] = { false, };
int N = 10000;
for (int i = 1; i <= N; i++) {
check[makeNum(i)] = true;
}
for (int i = 1; i <= N; i++) {
if (check[i] == false)
cout << i << endl;
}
return 0;
}