[백준/파이썬] 1065번 한수 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1065번 한수
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

각 자리수가 등차수열을 이루는 수를 한수라고 한다.

(예: 1234567, 8462, 159, 2222 등)

1이상 n이하의 한수의 개수를 출력하라.

코드

import sys
sys.setrecursionlimit(10000)

n = int(input())

def count_hansu(n):
    if n > 0:
        sliced = list(map(int, list(str(n))))
        sub_before = -11
        for i, _ in enumerate(sliced):
            try:
                sub = sliced[i]-sliced[i+1]
                if(sub_before != -11 and sub != sub_before):
                    return count_hansu(n-1)
                sub_before = sub
            except IndexError:
                break
        return 1 + count_hansu(n-1)
    else:
        return 0

print(count_hansu(n))

설명

우선, 이번 알고리즘은 재귀로 구현할 것이기 때문에 sys.setrecursionlimit(10000)를 호출합니다.

이 메소드는 최대 재귀 호출 횟수를 설정하는 메소드입니다. n이 1000이하이므로 1001만 해도 될테지만 넉넉잡아 10000으로 했습니다.

파이썬은 기본 재귀 깊이가 (구현마다 다르다고는 하지만 대개)1000으로 제한되어 굉장히 적기 때문에, 이를 호출하지 않으면 런타임 에러가 발생합니다.

count_hansu(n)은 1이상 n이하 한수의 개수를 반환하는 메소드입니다.

sub_before는 현재 자리까지의 공차를 저장하는 변수입니다.

sub는 현재 자리와 다음 자리의 차를 계산한 값입니다.

만약, sub_before!=-11이라면, 한번이상 공차가 계산된 상태이고, 이 값과 다음 자리와의 차가 다르다면 해당 수는 한수가 아니므로 count_hansu(n-1)를 반환합니다.

그렇지 않고 끝자리 까지 도착해서 IndexError를 발생시킨다면 모든 자리수가 등차수열을 이루고 있다는 뜻이므로, 한수 하나를 추가하여 1 + count_hansu(n-1)를 반환합니다.

종료조건으로는 n이 0이하인 경우 0을 반환하도록 했습니다.

---

• 백준 문제풀이 전체 목록 보기

---