백준 10844번(쉬운 계단 수) 파이썬 풀이 및 테스트 케이스: 뒤에서부터 채워나가기

https://www.acmicpc.net/problem/10844 solved.ac 기준 실버 1. 정말 오랜만에 재귀 함수 개념을 써먹는다.

계단수라는, 예를 들면 1234543456765 같은 수가 총 몇 개 존재하는지를 알아내는 문제. 물론 간단한 재귀함수를 사용해도 답을 내는 데는 문제가 없지만, N = 100일 때 가능한 가짓수는 무려 89,207,240,240,093,898,472,018,404,112가지다. 1씩 더해 가는 재귀함수로는 당연히 무리다.

좀 더 머리를 써야 한다. 테스트 케이스 1 9 2 17 5 116 10 2986 50 894685264 100 18404112 순식간에 답을 도출할 수 있어야 한다.

예를 들어 10000을 입력해도 몇 초 내로 817374798라는 답을 낼 수 있을 만큼. N = int(input()) how_many_dic = dict() # 뒤에서부터 채워나갑시다. def how_many(i, j): # i는 해당 자리의 수, j는...

백준 10844번(쉬운 계단 수) 파이썬 풀이 및 테스트 케이스: 뒤에서부터 채워나가기

https://www.acmicpc.net/problem/10844 solved.ac 기준 실버 1. 정말 오랜만에 재귀 함수 개념을 써먹는다. 계단수라는, 예를 들면 1234543456765 같은 수가 총 몇 개 존재하는지를 알아내는 문제. 물론 간단한 재귀함수를 사용해도 답을 내는 데는 문제가 없지만, N = 100일 때 가능한 가짓수는 무려 89,207,240,240,093,898,472,018,404,112가지다. 1씩 더해 가는 재귀함수로는 당연히 무리다. 좀 더 머리를 써야 한다. 테스트 케이스 1 9 2 17 5 116 10 2986 50 894685264 100 18404112 순식간에 답을 도출할 수 있어야 한다. 예를 들어 10000을 입력해도 몇 초 내로 817374798라는 답을 낼 수 있을 만큼. N = int(input()) how_many_dic = dict() # 뒤에서부터 채워나갑시다. def how_many(i, j): # i는 해당 자리의 수, j는

blog.naver.com/jpg06008/223514441792