ps:problems:boj:1065
한수
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 1065 |
문제명 | 한수 |
레벨 | 실버 4 |
분류 |
기초 |
시간복잡도 | O(n) |
인풋사이즈 | n<=1000 |
사용한 언어 | Python |
제출기록 | 29200KB / 68ms |
최고기록 | 52ms |
해결날짜 | 2021/11/15 |
태그 |
풀이
- 한수라는 용어는 처음 들어봤는데, 원래 있는 말인지 이 문제에서 지어낸 말인지조차도 모르겠다
- 숫자가 2개면 항상 등차수열이므로, 2자리수 숫자는 무조건 한수이다. 자릿수가 더 커지면 등차수열인지 일일히 체크를 해야 하는데, N이 1000 이하다 보니, 1000은 한수가 아니니 제외하면.. 등차수열 체크를 해야하는 것은 3자리수 숫자들 뿐이다. 그냥 숫자 abc에 대해서 a+c==2*b인지만 보면 된다.
- 사실 수학적 성질을 고려하면 더 빠르게 구할수 있는 방법도 많이 있다. 예를 들면 [x*100, (x+1)*100) 구간에서 한수는 5개뿐인데, 이런 것들을 활용하면 루프 범위를 훨씬 줄여나갈수도 있다. 하지만 그냥 구해도 충분히 빠르므로 그냥 n까지 다 루프를 돌며 체크하는 것으로 구현.
코드
"""Solution code for "BOJ 1065. 한수".
- Problem link: https://www.acmicpc.net/problem/1065
- Solution link: http://www.teferi.net/ps/problems/boj/1065
"""
def is_hansu(n):
if n < 100:
return True
a, b, c = n // 100, n // 10 % 10, n % 10
return b + b == a + c
def main():
N = int(input())
print(sum(1 for x in range(1, N + 1) if is_hansu(x)))
if __name__ == '__main__':
main()
ps/problems/boj/1065.txt · 마지막으로 수정됨: 2021/11/15 07:18 저자 teferi
토론