백준 25421 python

HJ seo·2022년 8월 12일
0

Coding Test(Python)

목록 보기
16/45

문제 링크

설명

내가 좋아하는 dp문제.
문제가 짧아 설명은 사진째로 올린다.

내가 풀이한 방법은 조건에 부합하면서 특정 숫자로 끝나는 숫자들의 갯수를 카운트 한 것이다.

예를 들어 2로 끝나는 3자리 숫자를 생각해보자. 그 숫자들은 차례대로
21X, 22X, 23X, 24X가 된다. 그리고 dp를 사용한다면 이전 배열의 0번째 항부터 3번째 항까지 sum을 해준 값이 들어가야 할 것이다.

그리고 충분히 큰 수에 대해서는 너무 메모리를 많이 잡아먹게 되므로 수를 넣을때마다 987654321을 나눈 나머지를 집어넣었다.(n의 바운더리가 10만까지인 subtask 문제이기 때문에 나머지를 집어넣는 것이 아니라면 중간에 메모리초과로 낮은 점수를 받을 가능성이 농후하다.)

그리고 마지막으로 우리가 구할 것은 특정 자리가 아닌 조건에 부합하는 모든 숫자의 갯수를 987654321로 나눈 나머지인 것을 유념하자.


풀이 코드

num = [1 for _ in range(9)]

n = int(input())

while n != 1:
    tmp = []
    for i in range(9):
        tmp.append(sum(num[max(0, i - 2):min(10, i + 3)]) % 987654321)
    num = tmp
    n -= 1

print(sum(num) % 987654321)

cf1. 굳이 이중으로 list를 넣어서 하기 싫어서 잦은 list 업데이트를 하게 되었다. 이 경우 장점은 큰 메모리를 잡아먹는 이중리스트가 없는 대신 속도가 조금 떨어진다.

cf2. 워낙 오늘 올리려 한 포스팅은 내용이 점점 길어지고 있다... 좀 짤라서 올려야 하려나...ㅠㅠ

profile
다양한 분야에 관심이 많은 초보 개발자 입니다.

0개의 댓글