백준 1065번: 한수

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

1. 문제

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

2. 알고리즘

키워드 - 수학, 구현

문제를 접근 하기 위해서는 먼저 등차 수열이 무엇인지를 이해 해야 한다.

수학에서, 등차수열(等差數列, 문화어: 같은차수렬, 영어: arithmetic sequence)은 연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다. 예를 들어 1, 3, 5, 7, 9, ...은 등차수열이다. 이때 두 항의 차이는 이 수열의 모든 연속하는 두 항들에 대해서 공통적으로 나타나는 차이므로, 공차(common difference)라고 한다. 예를 들어, 앞의 수열의 공차는 2이다.

문제에서 정의 된 예를 보면 321 의 각각의 숫자의 공차는 -1 이다.

135 의 숫자의 공차는 2 이다.

문제의 조건을 나누어 보자

- 1의 자리숫자 -> 모두 한수

- 10의 자리 숫자 -> 모두 한수

결국 1 부터 100 사이의 수는 100 을 제외한 99 가 한수이다.

3. 코드

#include <iostream>
#include <algorithm> // min
#include <math.h>
#include <string>
#include <vector>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);  // scanf 안쓸 경우 쓰세요. Cin 사용시
    int n; cin >> n;
 
    int count = 0;
    int cand[3] = { 0, };
 
    for (int i = 1; i <= n; i++) {
        if (i > 0 && i < 100) {
            count++;
        }
        else if(i == 1000){
            break;
        }
        else {
            int cand2 = i;
            for (int j = 0; j < 3; j++) {
                cand[j] = cand2 % 10;
                cand2 = cand2 / 10;
            }
 
            if (cand[0] - cand[1] == cand[1] - cand[2])
                count++;
        }
    }
    cout << count << "\n";
 
    return 0;
}