백준 1065번 <한수> [파이썬]

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

1065번: 한수

 

한수 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

119545

64052

53514

53.353%

문제

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

입력

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

출력

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

예제 입력 1

110

예제 출력 1

99

예제 입력 2

1

예제 출력 2

1

예제 입력 3

210

예제 출력 3

105

예제 입력 4

1000

예제 출력 4

144

 

 

일단 이 문제는 '한수'라는 것에 대해서 제대로 아는 것이 중요하다!

문제가 이해가 안되는 문제는 여태 이 문제가 처음이다!!!

일단 간단하게 예를 들어 설명하면 

예를 들어 123 이라는 숫자는 한수일까? 

한수이다. 그 이유는? 123을 통째로 보지 말고 1과 2와 3을 따로따로 보는 것이다. 

즉, 하나의 숫자의 각 자릿수들을 개별적으로 보는 것이다. 

그렇다면, 1과 2와 3으로 따로따로 봤기 때문에, 1과 2는 +1 , 2와 3은 +1 

그렇기 때문에 이는 한수이다.

 

더불어서 1부터 99까지는 한수이다!

그 이유는 1-9까지는 0이라는 공차를 가진 것이라고 보고 등차수열로 보면 된다. 

그 이유는 옛날부터 그래왔으니 그런 것이라고 알고 있다. 나는 개발을 공부하는 것일 뿐 

수학의 유래는 몰라요 ㅠㅠ 

쨋든 돌아가서 10-99까지도 공차가 +1 혹은 -1인 등차수열이다.

예를 들면 12는 +1로 15는 +4로 등차수열이고,

반대로 41은 -3으로 등차수열이다!

 

마지막으로 세자리 수는 좀 고려해야 되는데, 위에서 말했듯이 123은 등차수열이지만,

100과 101은 등차일까? 아니다. 1과 0과 0은 공차가 -1 그리고 0이다. 그렇다면 등차수열이 아니다.

또한 1과 0과 1은 공차가 -1과 +1로 다른 공차를 지녀 등차수열이 아닌 것이다!

 

이렇게 한수에 대한 개념을 가지고 알고리즘을 만들었다!

import math

def check(n):
    if n < 100:
        return 1
    elif 100 <= n < 1000:
        x = []
        temp = n
        for i in range(3):
            a = temp % 10
            x.append(a)
            temp = math.floor(temp / 10)
        list.reverse(x)
        d1 = x[1] - x[0]
        d2 = x[2] - x[1]
        d3 = x[0] - x[1]
        d4 = x[1] - x[2]
        if d1 == d2 or d3 == d4:
            return 1
        else:
            return 0
    else:
        return 0
    
n = int(input())
global cnt
cnt = 0
if n != 1:
    for i in range(1,n+1):
        temp = check(i)
        cnt = cnt + temp
    print(cnt)
elif n == 1:
    print(1)

이렇게 나왔는데, 함수가 본문보다 길다.

우선 함수에 대해서 어떻게 풀었냐하면

def check(n):
    if n < 100:
        return 1
    elif 100 <= n < 1000:
        x = []
        temp = n
        for i in range(3):
            a = temp % 10
            x.append(a)
            temp = math.floor(temp / 10)
        list.reverse(x)
        d1 = x[1] - x[0]
        d2 = x[2] - x[1]
        d3 = x[0] - x[1]
        d4 = x[1] - x[2]
        if d1 == d2 or d3 == d4:
            return 1
        else:
            return 0
    else:
        return 0

이렇게 했는데, 앞서 말했듯이 1-99까지는 한수이다. 그렇기에 return 값으로 1을 주었는데, 위에 본문에서는 

return값을 0이나 1로 주어 갯수를 더하는 형식으로 최종 출력 값을 뽑아내는 것으로 구조를 만들어놔서 

100이하의 수는 1을 return하는 것으로 만들었고,

 그 이외의 100이상 1000 미만의 값들은 각 자리수들로 나누어 list에 담고

중간에 reverse는 자리수를 나눌 때 나머지로 나누어서 그냥 다시 기존의 수로 만들고 싶어서 추가했다,,ㅎ 

다 짜고 나서 생각해보니까 굳이 필요없는 것 같기는 한데, 그래도 이걸로 디버깅 할 때 도움이 됐다!

 

다시 돌아와서 d1,d2,d3,d4로 공차를 구해서 -이거나 +이거나 다 구별해서 공차가 같은지 구별을 해줌으로써

함수를 구성했다!

 

1000같은 경우는 그냥 예외처리로 return 값으로 0 주고 끝냈다..

 

이러면 설명은 다 한 것 같다

 

시간이 너무 늦었는데, 눈이 너무 무겁다

앞으로는 조금 더 이른 시간에 해야겠다

화이팅!!