https://www.acmicpc.net/problem/4673
๋ฌธ์
์ ํ ๋๋ฒ๋ 1949๋ ์ธ๋ ์ํ์ D.R. Kaprekar๊ฐ ์ด๋ฆ ๋ถ์๋ค. ์์ ์ ์ n์ ๋ํด์ d(n)์ n๊ณผ n์ ๊ฐ ์๋ฆฌ์๋ฅผ ๋ํ๋ ํจ์๋ผ๊ณ ์ ์ํ์. ์๋ฅผ ๋ค์ด, d(75) = 75+7+5 = 87์ด๋ค.
์์ ์ ์ n์ด ์ฃผ์ด์ก์ ๋, ์ด ์๋ฅผ ์์ํด์ n, d(n), d(d(n)), d(d(d(n))), ...๊ณผ ๊ฐ์ ๋ฌดํ ์์ด์ ๋ง๋ค ์ ์๋ค.
์๋ฅผ ๋ค์ด, 33์ผ๋ก ์์ํ๋ค๋ฉด ๋ค์ ์๋ 33 + 3 + 3 = 39์ด๊ณ , ๊ทธ ๋ค์ ์๋ 39 + 3 + 9 = 51, ๋ค์ ์๋ 51 + 5 + 1 = 57์ด๋ค. ์ด๋ฐ์์ผ๋ก ๋ค์๊ณผ ๊ฐ์ ์์ด์ ๋ง๋ค ์ ์๋ค.
33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...
n์ d(n)์ ์์ฑ์๋ผ๊ณ ํ๋ค. ์์ ์์ด์์ 33์ 39์ ์์ฑ์์ด๊ณ , 39๋ 51์ ์์ฑ์, 51์ 57์ ์์ฑ์์ด๋ค. ์์ฑ์๊ฐ ํ ๊ฐ๋ณด๋ค ๋ง์ ๊ฒฝ์ฐ๋ ์๋ค. ์๋ฅผ ๋ค์ด, 101์ ์์ฑ์๊ฐ 2๊ฐ(91๊ณผ 100) ์๋ค.
์์ฑ์๊ฐ ์๋ ์ซ์๋ฅผ ์ ํ ๋๋ฒ๋ผ๊ณ ํ๋ค. 100๋ณด๋ค ์์ ์ ํ ๋๋ฒ๋ ์ด 13๊ฐ๊ฐ ์๋ค. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97
10000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ํ ๋๋ฒ๋ฅผ ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ ๋ ฅ์ ์๋ค.
์ถ๋ ฅ
10,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ํ ๋๋ฒ๋ฅผ ํ ์ค์ ํ๋์ฉ ์ฆ๊ฐํ๋ ์์๋ก ์ถ๋ ฅํ๋ค.
ํ์ด
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int d (int n){
int tmp = 0, divisor = 10, sum = 0;
vector <int> v;
//์ฃผ์ด์ง ์ ์ n์ ๊ฐ ์๋ฆฌ์ซ์๋ค์ v์ ๋ฃ๋๋ค
while(true){
tmp = n % divisor;
if(tmp == n){
v.push_back(tmp / (divisor/10));
divisor *= 10;
break;
}
v.push_back(tmp / (divisor/10));
divisor *= 10;
}
//๊ฐ ์๋ฆฌ์ซ์๋ค์ ํฉ sum
for(int i=0; i<v.size(); i++){
sum += v[i];
}
return sum + n;
}
int main() {
vector <int> value;
//๋ฒกํฐ value์์ 1๋ถํฐ 10000๊น์ง ์๋ค์ d๊ฐ๋ค ์ ์ฅ
for(int i=1; i<10001; i++){
value.push_back(d(i));
}
for(int i=1; i<10001; i++){
//value์ i๊ฐ ์๋ค๋ฉด i ์ถ๋ ฅ
if(find(value.begin(), value.end(), i) == value.end()){
cout << i << "\n";
}
}
return 0;
}
+)
์ฃผ์ด์ง ์ซ์์ ๊ฐ ์๋ฆฌ ์ซ์๋
์์ ๊ตฌํ๋ ๊ฒ๊ณผ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ๊ตฌํ๋ค
++)
while(num>0) {
sum = num % 10
num /= 10
}
ํจ์ฌ ์ฌ์ด ์ฝ๋๊ฐ ์์๋ค..
'๐ฆ Chango > ๐ฅ BOJ ๋จ๊ณ๋ณ๋ก ํ์ด๋ณด๊ธฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ][C++] ๋ฐฑ์ค 11654๋ฒ: ์์คํค ์ฝ๋ (0) | 2021.09.09 |
---|---|
[BOJ][C++] ๋ฐฑ์ค 1065๋ฒ: ํ์ (0) | 2021.09.06 |
[BOJ][C++] ๋ฐฑ์ค 15596๋ฒ: ์ ์ N๊ฐ์ ํฉ (0) | 2021.09.02 |
[C++][BOJ] ๋ฐฑ์ค 4344๋ฒ: ํ๊ท ์ ๋๊ฒ ์ง (0) | 2021.09.02 |
[C++][BOJ] ๋ฐฑ์ค 8959๋ฒ: OXํด์ฆ (0) | 2021.08.21 |