[ C++ ] Code-Up 2102: 배수 (Hard)

 

안녕하세요? 수구리입니다!

 

이번 포스팅에서는 마찬가지로 배수와 관련된 문제를 풀어보려고 하는데요~

 

처음에 이진수로 해서 풀어보려했지만 실패..

 

암튼 문제는 아래 링크에 걸어두었습니다..!

 

문제를 보고 풀이를 보시면 무슨 소린지 이해하실 수 있을겁니다!

 

 

[ 문제 ] 2102. 배수 (Hard)

배수 (Hard)

 

[ 나의 풀이 ]

#include <iostream>
#include <algorithm>
using namespace std;

unsigned long long N;
const unsigned long long lim = 11111111111111111111;
unsigned long long minVal = UINT64_MAX;

void solution(unsigned long long start) {
    if (start % N == 0)
        minVal = min(minVal, start);
    
    if (start > lim / 10)
        return;
    
    solution(start * 10 + 1);
    solution(start * 10);
}

int main()
{
    cin >> N;
    
    if ( N > lim ) {
        cout << 0;
        return 0;
    }
    
    solution(1);
    
    if (minVal == UINT64_MAX)
        cout << 0;
    else cout << minVal;
    return 0;
}

 

[ 설명 ]

1. 사용자로부터 자연수 N 값을 입력받는다. 이때, N의 범위는 lim 보다 작아야 한다.

(2^64는 10^20 보다 작으므로 0과 1을 사용해서 만들 수 있는 가장 큰 값은 1이 20개로 이뤄져야 함)

2. 시작값 (=start)를 1부터 재귀를 통해 10을 곱하거나, 10을곱하고 1을 더해서 십진수를 이진수처럼 계산한다.

3. 결과를 출력한다.