[Python] 백준 1065번 - 한수

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

1065번: 한수

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 브루트포스 알고리즘

 

문제

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

입력

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

출력

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

 

---

이번에도 문제를 이해하는데 약간의 시간이 걸렸다.

 

처음에 내가 이해한 방법은

 

예를 들어 135 라는 숫자가 한수인지 확인할 경우

 

0 1 3 5 로 확인하여

 

각 등차가 1 2 2 로 한수가 아니라고 판단했다.

 

하지만 이는 잘못된 방식이었고 앞의 0은 생각하지 않은 1 3 5만 확인하여 각 등차가 2인 등차수열이 된다.

 

import sys
import math
input = sys.stdin.readline

n = int(input())
cnt = 0

for i in range(1, n+1):
    a = i // 1000
    b = (i // 100) % 10
    c = (i // 10) % 10
    d = i % 10
    ga = a-b
    gb = b-c
    gc = c-d
    
    if 0 < i < 100:
        cnt += 1
    else:
        if gb == gc and i != 1000:
            cnt+=1

print(cnt)

사실 위 방식은 하나하나 확인하는 방법이고

 

사실상 n이 100 이하일 경우엔 무조건 n개만큼의 한수가 발생한다.

 

1~99 는 모두 한수가 되기 때문이다.

 

최댓값인 1000은 당연히 한수가 안되기 때문에 빼주었다.

 

위의 코드도 개선할 점이 있는 코드이나 시간이 빠르게 나와 마무리하였다.