백준 1065 S4 한수

Date/Lastmod

03-10/25 03-11/25

Section

PS

Title

백준 1065 S4 한수

Ps-Tags

Solved

03-09/25

#¹ 접근

$[1, N]$ 범위의 모든 정수가 한수인지 아닌지 검사한다면 복잡도는 일단 $O(N)$이다.

$[1, N]$에 속하는 모든 정수 $n$에 대해서:

• 모든 자릿수를 순회하기 위해서 일단 각 자리별로 쪼개야 하고, 여기에는 $O(len(n))$이 소요된다.
• 쪼갠 후 각 자릿수들의 공차가 일정한지 확인하며 또다시 $O(len(n))$이 소요된다.

그러므로 전체 복잡도는 아마 $O(N \cdot 2len(n))$ 일 것이고, $len(n)$은 최대 3이므로 그냥 $O(N)$이라고 보아도 무방하다.

그러므로 그냥 무식하게 범위 내의 정수를 순회하며 한수인지 아닌지 판별하여도 제한 시간 2초는 매우 넉넉할 것이다.

#¹ 알고리즘

• 한수 갯수를 0이라고 한다.
• 1부터 $N$ 사이의 모든 수 $n$ 에 대해 다음을 진행한다:
  • $n$을 10진수의 각 자릿수별로 쪼갠다.
  • 자릿수가 1개이거나 2개이면 무조건 한수라고 판정하여 한수 갯수를 하나 증가시킨다. 그리고 다음 $n$으로 넘어간다.
  • $n$의 각 자릿수를 순회하며 공차가 일정한지 판단한다.
    • 만일 하나라도 일정하지 않은 공차가 발견되면, 한수가 아니므로 빠르게 다음 $n$으로 넘어간다.
  • 모두 공차가 일정하다면, 한수인 것이므로 한수 갯수를 하나 증가시킨다.

#¹ 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool is_hansu(int n) {
    string sn = to_string(n);

    // 숫자의 길이가 1, 2이면 그냥 한수 (비교할 것이 없음)
    if (sn.size() <= 2) 
      return true;

    // 초항을 이용해 공차를 계산해둠
    int a_0 = *sn.cbegin() - '0';
    int a_1 = *(++sn.cbegin()) - '0';
    int d = a_1 - a_0;

    // 두 번째 항 부터 공차를 계산 해봄
    for (auto it = sn.cbegin() + 1; it != sn.cend(); ++it) {
      // 마지막 항에 도달했으면 종료
      if (it + 1 == sn.cend()) 
        break;

      // 공차 계산해보고 `d`랑 다르면 한수 아니므로 빠른 종료
      int a_n_0 = *it - '0';
      int a_n_1 = *(it + 1) - '0';

      if (a_n_1 - a_n_0 != d) 
        return false;
    }

    // 여기까지 도달한 경우 모든 공차가 동일한 것이므로 한수
    return true;
}

int main() {
  int N; cin >> N; // [1, 1'000]

  int count = 0;

  for (int n = 1; n <= N; ++n) {
    if (is_hansu(n)) 
      ++count;
  }

  cout << count;
}

// TODO: 반복자 섞어 쓰기

#¹ 자연수를 각 자릿수별로 쪼개는 법

아마도 “$n$을 10진수의 각 자릿수별로 어떻게 쪼갤 것인가,” 가 이 문제에서 가장 달라지는 부분이 아닐까 싶다.

#² 문자열로 통째로 바꾸기

우선 나는 정수를 그냥 문자열로 통째로 바꾸는 방법을 사용하였다.

std::string sn = std::to_string(n); // 123 -> "123"

for (char c: sn) {
  cout << c << ": " << c - '0' << '\n';
}

정수에 std::to_string을 쓰면 이쁘게 문자열로 바뀌고, 각 자릿수 문자는 char이므로 '0'을 빼주면 실제 그 문자가 나타내는 정수값으로 변환할 수 있다.

#² 벡터 등을 이용하기

int n = 12345;

std::vector<int> digits; int c = n;
while (c != 0) {
  digits.push_back(c % 10);
  c /= 10;
}

for (int i = 0; i < digits.size(); ++i) {
  std::cout << i << ": " << digits[i] << '\n';
  /*
    0: 5
    1: 4
    2: 3
    3: 2
    4: 1
  */
}

10으로 나눈 나머지와 몫으로 자릿수를 판별해 나가는 방식이다.

위 코드는 높은 자릿수의 숫자가 가장 오른쪽에 저장되므로 주의해야 한다.

순방향 그대로 저장하려면 push_front를 쓰거나, 자릿수를 먼저 계산한 후 vector의 크기를 설정하고 거꾸로 집어넣는 수밖에 없다.