[BAEKJOON] 1065 - 한수 (C++)

문제 링크
난이도 : Silver 4
(solved.ac 2023.09.29. 기준)

문제

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.

알고리즘

수학
브루트포스

풀이

1부터 n까지의 한수의 개수를 구해야 하기 때문에 반복문으로 1부터 n까지의 모든 수를 한수인지 판별하여 개수를 세는 count 변수에 +1을 하는 방법으로 한수의 개수를 구할 수 있다.

자리수가 2개까지의 양의 정수(1~99)들은 모두 각 자리수가 등차수열을 이루는 한수이기 때문에 그냥 count 변수에 +1을 한다. 하지만 100부터 N까지의 수들은 한수인지 판별하여야 한다.

각 자리 수의 차이를 구해야 하기 때문에 각 자리의 수를 추출하기 위해 <string>에 있는 to_string() 함수를 이용하였다. to_string() 함수는 int형을 string형으로 변환해준다.

to_string(156) == "156"  //true
to_string(156)[0] == '1' //true
to_string(156)[1] == '5' //true
to_string(156)[2] == '6' //true

숫자의 첫번째 자리 수와 두번째 자리 수의 차이를 먼저 구하여 diff 변수에 저장한 다음, 두번째 자리 수부터 그 다음 자리 수와의 차이가 diff와 다르다면 등차수열이 아니기 때문에 한수가 아니다. 한수가 아니라면 다음 수로 건너뛴다. 이러한 방식으로 1부터 N까지 모두 판별한다면 한수의 개수를 구할 수 있다.

코드

#include <iostream>
using namespace std;
int main()
{
    int n, count = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) // 1부터 n까지 모든 수를 브루트포스
    {
        if (i <= 99) // 99까지는 모든 양의 정수가 한수이므로 확인할 필요가 없다.
        {
            count++;
            continue;
        }
        string num = to_string(i);               // 각각의 자리 수를 추출하기 위해 숫자 i를 string으로 변환
        int diff = num[1] - num[0];              // 첫번째 자리 수와 두번째 자리 수의 차이
        bool skip = false;                       // 한수가 아닌 수를 건너뛰기 위해
        for (int j = 1; j < num.size() - 1; j++) // 두번째 자리 수부터 마지막 자리 수까지 비교
        {
            if (num[j + 1] - num[j] != diff) // j번째 자리 수와 j+1번째 자리 수의 차이가 diff와 다르다면 한수가 아니다.
            {
                skip = true;
            }
        }
        if (skip) // 한수가 아니면 +1 하지 않고 다음 수로 건너뛴다.
        {
            continue;
        }
        count++;
    }
    cout << count;
    return 0;
}