[백준] 한수 - 완전탐색 (Brute Force) (python)

1. 문제 설명

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

 

---

2. 입출력 조건

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

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

 

---

3. 입출력 예제

 

입력	출력
110	99
1	1
210	105
1000	144

 

---

4. 나의 풀이

문제를 풀기 전, 이해하는데 시간이 좀 걸렸고, 심지어 등차수열 판별하는 알고리즘을 잘못 짜서 문제 난이도보다 시간이 오래 걸렸다. 단순히 모든 경우를 탐색하여 답을 내기만 하는 브루트포스 예제이다.

 

def progression(a):
    l = [int(i) for i in list(str(a))]
    d = l[1] - l[0]
    for i in range(1, len(l)):
        if l[i] - l[i-1] != d:
            return False
    return True

n = int(input())

if n < 100:
    print(n)
else:
    answer = 0
    for j in range(100, n + 1):
        if progression(j) == True:
            answer += 1
    print(answer + 99)

 

프로그래머스와 달리, solution 함수에 짜는 형식이 아닌, 입력을 받고 print로 답을 출력하는 형식이라 적응하는데에도 시간이 조금 걸렸다. (파이썬으로 input을 받는 것도 순간 까먹는 바람에 구글링해서 찾음ㅠㅅㅠ) 등차수열의 경우, 항이 2개까지는 무조건 성립하므로 99까지의 숫자는 모두 등차수열이 된다고 간주해 숫자 자체를 출력해주고, 100이 넘어가는 경우에는 등차수열 알고리즘으로 판별하게 해주었다.

 

 

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

1065번: 한수