[Seop's의 코드풀이] 백준 1065 한수

이번에 풀어 볼 문제는 백준 1065번인 한수 라는 문제입니다.

문제는 다음과 같습니다.

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

1065번: 한수

 

문제를 살펴보면 각 자릿수가 등차수열을 이루는 수를 구하는 문제입니다.

즉 123 은 각 자릿수의 차이가 1임으로 이에 해당됩니다.

 

그리고 한자릿수와 두자리수는 각자리수의 차이가 동일할 수밖에 없으므로 모두 해당됩니다.

 

즉 1~99 까지 99개의 수는 문제에서 정의한 한수 입니다.

 

입력되는 수가 1000 이하인 자연수이니 우리는 3자릿수에서 한수를 찾기만 하면 됩니다.

 

저는 이 문제를 2가지 방법으로 풀었습니다.

1. 3자릿수에 해당하는 한수 모두 구해서 갯수 세기

2. 입력된 수 이전까지 반복문을 돌려 한수인지 확인하기

 

먼저 첫번째 방법부터 보면 굉장히 단순합니다.

3자릿수 중에서 한수가 될 수 있는 수는 다음과 같습니다.

    han_dict = {
        1: [111,123,135,147,159], 2: [210,222,234,246,258], 3: [321,333,345,357,369],
        4: [420,432,444,456,468], 5: [531,543,555,567,579], 6: [630,642,654,666,678],
        7: [741,7536,765,777,789], 8: [840,852,864,876,888], 9: [951,963,975,987,999]
    }

생각보다 그리 많지 않습니다.

신기하게도 각 자리수에 해당하는 숫자가 5개씩으로 동일하며 총 45개입니다.

몇개인지 확인하는 방법은 간단합니다.

 

(n 을 100으로 나눈 후 값 -1 )*5  + (n을 100을 나눈 후의 키값 중 n 보다 작거나 같은것 더하기)

 

첫번째 방법의 코드는 다음과 같습니다.

def soluction(n) :

    if n <= 99 :
        return n
    elif n == 100 :
        return 99
    elif n == 1000 :
        return 144
    answer = 99
    han_dict = {
        1: [111,123,135,147,159], 2: [210,222,234,246,258], 3: [321,333,345,357,369],
        4: [420,432,444,456,468], 5: [531,543,555,567,579], 6: [630,642,654,666,678],
        7: [741,7536,765,777,789], 8: [840,852,864,876,888], 9: [951,963,975,987,999]
    }
    k = n//100
    answer += 5*(k-1)
    for i in han_dict[k] :
        if i <= n :
            answer += 1
    return answer


N = int(input())
print(soluction(N))

 

2번째 방법은 한수를 직접 확인하는 방법입니다.

생각보다 간단합니다.

if (첫번째 자리 - 두번째 자리) == (두번째 자리 - 세번째 자리)

이 식이 성립할때 정답에 1을 추가해 줌으로서 문제를 해결 할 수 있습니다.

 

전체 코드는 다음과 같습니다.

def soluction(n) :
    if n <= 99 :
        return n
    elif n == 1000 :
        return 144
    else :
        answer = 99
        for i in range(100, n+1) :
            a1 = i//100
            a2 = i%100//10
            a3 = i%100%10
            if (a1 - a2) == ( a2 - a3) :
                answer += 1
    return answer

N = int(input())
print(soluction(N))