[백준] 1065번 한수 C++ 풀이

99​

210​

---

알고리즘 분류

• 수학
• 브루트포스 알고리즘

---

문제 설명

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

---

입력 설명

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

---

출력 설명

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

---

예제 입력

110

1

210

1000

500

---

예제 출력

99

1

105

144

119

---

아이디어

각 자리의 숫자가 등차수열을 이루는지 확인해야 한다.

우선 1자리뿐인 1~9는 모두 한수이다.

또한 10~99는 각 자리의 숫자가 모두 등차수열을 이루므로 10~99도 모두 한수이다.

n은 1 이상 1000 이하의 자연수이고 1000은 한수가 아니다.

따라서 n이 1 ~ 99라면 n이 그대로 n이하의 수의 한 수의 개수가 되고

n이 100 ~ 1000이라면 100 ~ 999의 한수의 개수와 동일하다.

100 ~ 999는 모두 세 자리의 숫자이므로 각 자리의 숫자로 분할 가능하다.

이후 숫자가 커지는 등차수열인지 작아지는 등차수열인지 판단한 후 등차수열이 맞다면 한수의 개수를 증가시킨다.

 

---

알고리즘

n이 1~99라면 n을 출력한다.

n이 1000이라면 n을 999로 만든다.

i = 100에서 i <= n까지 i가 등차수열인지 아닌지를 판단하는 반복문을 수행한다.

i를 1의 자리 10의 자리 100의 자리 숫자로 분리한다.

각 자리의 숫자가 모두 동일하다면 한수의 개수를 증가시킨다.

 

100의 자리보다 10의 자리가 10의 자리보다 1의 자리 숫자가 크다면

1의 자리에서 10의 자리를 뺀 값과 10의 자리에서 100의 자리를 뺀 값이 일치하면 등차수열이다.

 

100의 자리보다 10의 자리가 10의 자리보다 1의 자리 숫자가 작다면

100의 자리에서 10의 자리를 뺀 값과 10의 자리에서 1의 자리를 뺀 값이 일치하면 등차수열이다.

 

이러한 경우에만 한수의 개수를 증가시키고 반복문 종료 후 한수의 개수를 출력한다.

---

코드

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n, cnt = 99;
    cin>>n;
    if(1<= n && n <= 99) {cout<<n; return 0;}
    else if(n==1000) n--;
    for(int i = 100; i <= n ; i++)
        {
            int ill = i%10, sib = (i/10)%10, bac = i/100;
            if(ill == sib && sib == bac) cnt++;
            else if(bac < sib && sib < ill)
            {
                int a = sib - bac;
                int b = ill - sib;
                if(a==b) cnt++;
            }
            else if(bac > sib && sib > ill)
            {
                int a = bac - sib;
                int b = sib - ill;
                if(a==b) cnt++;
            }
        }
    cout<<cnt;
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/1065

처음에는 한수가 무슨 의미인지 이해하기 어려웠다.

그리고 1~9는 다른 자리의 숫자가 없는데 이거는 한수인지 아닌지도 헷갈렸다.

하지만 곰곰이 생각해 보니 1 ~ 99의 숫자는 모두 한수였다!

그리고 n의 최댓값이 1000이다 보니 각 숫자의 자릿수를 구하는 문제도 수월했다.

만약 n의 최댓값이 더욱 컸다면 여러 개의 분기점을 나눠야 해서 더욱 복잡했을 것이다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!