1065 : 한수

• 실버 4

시간제한	메모리제한	정답비율
2초	128MB	54.286%

문제

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

input

0 < n <= 1000

output

1보다 크거나 같고, n보다 작거나 같은 한수의 개수를 출력

think

딱 보아하니 n 이하의 작업물들을 기록하면서 가야할 dp문제로 보인다. 점화식을 써보자… 고 했으나 풀고 보니, dp로 푸는 문제 같지만 사실상 사람들은 brute force로 완전탐색하면서 했던데 그게 훨씬 빠른 것 같다. 굳이 dp를 사용해야할 필요는 없는 것으로 보인다.

python

import sys, os

problem_num = "1065"

path = os.getcwd() + f"\\txt\\{problem_num}" + ".txt"
sys.stdin = open(path, "r")
input = sys.stdin.readline

n = int(input())

from typing import List
def spliting(x:int) -> List[int]:
    '''
    make a x:int to list of elements
    '''
    return [int(i) for i in str(x)]

class Hansu:
    def __init__(self,n):
        self.dp = [i for i in range(1,n+1)]
        
    def arithmetic_sequence(self):
        bool_list = []
        for i in self.dp:
            if (i < 100) or (spliting(i)[2] - spliting(i)[1] == spliting(i)[1] - spliting(i)[0]):
                bool_list.append(True)
            else:
                bool_list.append(False)
                    
        return bool_list.count(True)
            

print(Hansu(n).arithmetic_sequence())

144