BOJ 6679 - 싱기한 네자리 숫자

문제

1000부터 9999까지의 수 중 10진법, 12진법, 16진법에서 각 자릿수의 합이 모두 같은 수를 출력하라.

입력

입력 없음.

출력

조건을 만족하는 수를 한 줄에 하나씩 오름차순으로 출력한다.

예제

입력	출력
(없음)	`1000` `1030` `...`

풀이

1000~9999를 브루트포스로 순회하며 세 진법의 자릿수 합을 비교한다.

주어진 수를 base로 나누면서 나머지의 합을 구하는 calc 함수를 정의한다
1000부터 9999까지 각 수에 대해 10진, 12진, 16진 자릿수 합을 계산한다
세 값이 모두 같으면 해당 수를 출력한다

핵심 아이디어: 범위가 9000개로 제한되어 있어 각 수에 대해 3번의 진법 변환만 수행하면 충분하다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int calc(int num, int base)
{
  int ret = 0;
  while (num)
    ret += num % base, num /= base;
  return ret;
}
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  for (int i = 1000; i < 10000; ++i)
  {
    int dec = calc(i, 10);
    if (dec == calc(i, 12) && dec == calc(i, 16))
      cout << i << '\n';
  }
  return 0;
}

복잡도

시간: O(9000 * log N) (각 수에 대해 3개 진법의 자릿수 합 계산)
공간: O(1)

문제