[백준 BOJ 1065번] 한수 (C / C++ ) [브루트포스 알고리즘]

1065번: 한수 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	70269	36597	31026	52.169%

 

문제

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

 

입력

첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.

 

출력

첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.

 

예제 입력

110

1

210

1000

 

예제 출력

99

1

105

144

 

풀이

등차수열(等差數列, 문화어: 같은차수렬, 영어: arithmetic progression, AP 또는 arithmetic sequence)은 연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다. 예를 들어 1, 3, 5, 7, 9, ...은 등차수열이다. 이때 두 항의 차이는 이 수열의 모든 연속하는 두 항들에 대해서 공통적으로 나타나는 차이므로, 공차(common difference)라고 한다. 예를 들어, 앞의 수열의 공차는 2이다. (출처. 위키백과 등차수열 - 위키백과, 우리 모두의 백과사전 (wikipedia.org))

 

위 설명처럼 등차수열이란 수열의 자리수들의 차이가 모두 같은 수열을 뜻합니다.

한 자리 수는 모두 등차수열이고 두 자리수도 10이면 공차가 1인 등차수열, 99도 공차가 0인 등차수열입니다.

저는 그 점에서 일단 카운트를 99로 초기화하여 입력한 n의 값이 세 자리수 미만이면 해당 n의 값을 카운트로 다시 저장하게 하였습니다. 어차피 1~99까지는 모두 등차수열이므로 입력이 5면 출력값도 5이기 때문입니다.

입력값이 100 이상이면 반복문을 이용하여 등차수열을 판별하였는데, 저는 상한선이 1000까지이고 어차피 1000은 등차수열이 아니니 100의 자리 수, 10의 자리 수, 1의 자리 수를 각각 나누어 등차수열이면 카운트를 올리는 식으로 문제를 풀었습니다.

만약 현재 탐색 중인 값이 159이면 1과 5의 차, 5와 9의 차가 동일 할 때 등차수열로 판별하는데, 저는 100의 자리수와 1의 자리수의 합이 10의자리수를 두 배한 것과 같다는 규칙을 찾게 되어 그렇게 풀었습니다.

// (각 자리수의 차를 비교할 때)
if(L-M == M-R) cnt++;

위와 같은 조건식을 걸어도 정답은 똑같이 나옵니다.

다만, 제가 설계한 코드는 입력된 값 n이 1000 이하일 때만 고려하였으므로 더 높은 자리 수가 입력으로 들어올 때는 또 다른 설계를 고려해야 합니다.

코드

// 한수
// 브루트포스
#include<iostream>
int main(){
    int n,cnt=99;
    std::cin>>n;
    if(n<100)cnt=n;
    for(int i=100;i<=n;i++){
        int L=i/100;
        int M=i/10%10;
        int R=i%10;
        if(L+R==M*2)cnt++;
    }
    std::cout<<cnt;
}

 

1065번: 한수 (acmicpc.net)

1065번: 한수