[BF] 6679번 싱기한 네자리 숫자

6679번 싱기한 네자리 숫자

 

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

 

문제

싱기한 네자리 숫자란, [1000,9999]인 10진수 숫자중에서, 다음의 조건을 만족하는 숫자를 말한다.

• 숫자를 10진수, 12진수, 16진수로 나타낸 다음, 각각의 숫자에 대해, 각 숫자의 자리수를 더했을 때, 세 값이 모두 같아야 한다.

여러분은 싱기한 네자리 숫자를 모두 출력해야 한다.

 

입력

입력은 주어지지 않는다.

 

출력

싱기한 네자리 숫자를 오름차순으로 한줄에 하나씩 출력한다.

 

예제 입력

 

예제 출력

2992
2993
2994
2995
2996
2997
2998
2999
4470
4471
4472
4473
4474
4475
4970
4971
4972
4973
4974
4975
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469
5960
5961
5962
5963
6456
6457
6458
6459
7440
7441
7442
7443
7444
7445
7446
7447
7448
7449
7940
7941
7942
7943
8436
8437
8438
8439
9424
9425
9426
9427
9428
9429
9924
9925
9926
9927
9928
9929

 

해결방법

네자리의 경우의 탐색은 9000 의 시간이 소요된다

또한 각 수마다 진법변환에 5미만의 시간이 소요된다

따라서 최악의 경우 9000*15 = 135,000 이기 때문에 모든 경우를 탐색할 수 있다

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <algorithm>
using namespace std;

// 10진수 num 을 k진수로 변환하여, 각 자리 수를 더해서 반환하는 함수
int getSum(int num,int k){
    int quotient = num;
    int remainder;
    int sum = 0;
    
    while(1){
        remainder = quotient % k;
        quotient = quotient / k;
        
        sum += remainder;
        
        if(quotient < k){
            sum += quotient;
            break;
        }
    }
    
    return sum;
}

bool is_ok(int num){
    int decimal = 0;
    
    string dSum;
    dSum = to_string(num);
    for(int i=0; i<dSum.size(); i++){
        decimal += dSum[i] - '0';
    }
    
    int duo = getSum(num,12);
    int hexa = getSum(num,16);
    
    
    if(decimal == duo && decimal == hexa)
        return true;
    else
        return false;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for(int i=1000; i<=9999; i++){
        if(is_ok(i)){
            cout << i << "\n";
        }
    }
    
    return 0;
}