백준 알고리즘 | 1065 : 한수 (Python / 파이썬)

 

---

한수 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	54261	27475	23530	51.040%

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

1065번: 한수

---

문제

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

​

입력

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

​

출력

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

알고리즘 분류

브루트포스 알고리즘

---

백준 알고리즘 # 1065번 : 한수

n = int(input())
hansu = 0

for i in range(1, n + 1):
    if i < 100:             # 1부터 99까지는 모두 한수
        hansu += 1
    else:                   # 100부터는, ex) 123 -> 3 - 2 =  2 - 1
        n_str = list(map(int, str(i)))
        if n_str[2] - n_str[1] == n_str[1] - n_str[0]:
            hansu += 1

print(hansu)

풀이

먼저 한수란 "각 자리수들이 등차수열을 이루는 수"를 말하는 것이다.

이것을 달리 보면 등차수열을 생각해볼 수 있는데 1, 2, 3, ..., 99까지는 모두 한수에 속한다.

​

이것을 알고 풀이를 시작해보면 먼저 정수n을 입력받고, hansu를 0으로 초기화시켜놓는다.

다음으로 for문을 이용해서 1부터 정수 n보다 1많은 수 전까지, 즉 n까지 i를 반복해준다.

그리고 1부터 99까지는 모두 한수에 속하므로 if문을 이용해서 i가 100미만의 수일 때는 hansu에 1씩 더해준다.

​

그 다음 이외의 수들(else), 즉 100이상의 수일 때는

100이라는 숫자 자체를 str(문자열)로 각각 리스트화 시켜서

n_str = [1, 0, 0]

...

n_str = [1, 2, 3]

​

위와 같이 바꾼 뒤 각 자리수들끼리 등차수열을 이루는지 확인해주기 위해서

1의 자리수와 10의자리수를 빼보고, 10의자리수와 100의 자리수를 빼준다.

ex) 3 - 2 = 2 - 1 (1 = 1)

​

100의 자리수에서 10의 자리수를 뺀 것과, 10의 자리수와 1의 자리수를 뺀 것을 비교하는 결과도 동일하다.

ex) 1 - 2 = 2 - 3 (-1 = -1)

​

때문에 어떤 것을 택하든 이 조건이 같을 때는(if) hansu를 마찬가지로 1씩 더해준다.

그리고 range가 다 반복되는 동안 더해진 hansu를 출력해주면 풀이 끄-읏!👏

​

자세한 코드가 궁금하신 분들은 아래 GitHub 참고해주세요🙏

wook2124/Algorithm

 

최종 소스코드