사용자 도구

사이트 도구


ps:problems:boj:1065

한수

ps
링크acmicpc.net/…
출처BOJ
문제 번호1065
문제명한수
레벨실버 4
분류

기초

시간복잡도O(n)
인풋사이즈n<=1000
사용한 언어Python
제출기록29200KB / 68ms
최고기록52ms
해결날짜2021/11/15
태그

6단계

풀이

  • 한수라는 용어는 처음 들어봤는데, 원래 있는 말인지 이 문제에서 지어낸 말인지조차도 모르겠다
  • 숫자가 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()

토론

댓글을 입력하세요:
O F M W᠎ X
 
ps/problems/boj/1065.txt · 마지막으로 수정됨: 2021/11/15 07:18 저자 teferi