백준 1065번 파이썬 문제풀이(함수 - 한수) : 점화식으로 풀어보기

일반적인코드

def hansu(x: int):
    count = 0 #개수
    for i in range(1, x + 1):
        array = list(map(int, str(i))) #숫자를 문자열로 변환후 리스트에 넣으면 각각의 원소만 저장이가능하다. 이를 map함수를 이용해 각각의 원소를 다시 int형을 바꾸어 준다.
        if i > 99: #세자리수일때의 계산
            if array[1] - array[0] == array[2] - array[1]:
                count += 1
        elif i > 999: #네자리 수일때의 계산
            if array[1] - array[0] == array[2] - array[1] == array[3] - array[2]:
                count += 1
        else: #두자리수 미만일때는 그냥 count에다가 +1 해주기
            count += 1
    print(count)


n = int(input())
hansu(n)

-> 다음과 같은 코드는 문제에서 n이 1000보다 작거나 같다라고 했기 때문에 사용이 가능하다. 그러나 만약 n의 범위가 억단위를 벗어난다면 어떻게 해야될까? 일일이 범위를 설정할 수 없다. 따라서 점화식을 찾아야한다.

 

점화식을 이용한 풀이(집합자료형 이용)

def hansu(x: int):
    count = 0 #개수

    for i in range(1, x + 1):
        array = list(map(int, str(i))) #숫자를 문자열로 변환후 리스트에 넣으면 각각의 원소만 저장이가능하다. 이를 map함수를 이용해 각각의 원소를 다시 int형을 바꾸어 준다.
        if i > 99: #세자리수 이상일때의 계산
            difference = set([])  # 중복값을 허용안하는 집합자료형 set자료형으로 설정
            for j in range(1, array.__len__()):
                difference.add(array[j] - array[j - 1]) #중복을 허용하지 않기 때문에 만약 앞원소와 뒤의원소의 차가 같다면 계속해서 똑같은 원소가 삽입이 되지 않는다.
            if difference.__len__() == 1: #즉, 자리수 차 값이 똑같다는 것은 집합자료형 길이가 1인것과 마찬가지
                count += 1 #그럴때 개수에 +1 해주기
        else: #두자리수 미만일때는 그냥 개수에다가 +1 해주기
            count += 1
    print(count)

n = int(input())
hansu(n)

-> 각 코드의 설명은 주석으로 달아놨다.

 

조금 더 최적화한 코드 (22-01-17)

N = int(input())
count = 0  # 정답을 출력할 count 개수 출력

for i in range(10, N + 1):  # 10부터 N 까지 반복문을 돈다.
    temp = set()  # 중복을 허용하지 않는 Set 자료형 선언
    for j in range(len(str(i)) - 1):  # i를 문자열로 변경하여 그 길이의 -1 까지 돈다.
        temp.add(int(str(i)[j]) - int(str(i)[j + 1]))  # temp에 각 숫자 자리수의 차를 대입해준다.(ex) 123 일경우 2-1=1 , 3-2=1, 2개가 대입)
    if len(temp) == 1:  # 만약 temp의 길이가 1이라면
        count += 1  # 각 자리수가 등차수열 이므로 count값 1증가

if N < 10:  # N이 10보다 작다면 반드시 등차수열이므로 그 값을 출력
    print(N)
else:  # 만약 10보다 크다면
    print(count + 9)  # 1~9 는 등차수열 이므로 그 값을 count 값에 더해준다.