자릿수의 합이 같은 자연수 개수 구하기

Question

https://goor.me/UUHkN문제가 테스트에서는 잘 동작하는데 제출을 하면 fail이 많이 뜨고 시간 초과도 뜹니다.자릿수 L과 그 자릿수들의 합 S를 입력받아 자릿수의 합이 S가 되는 L자리 자연수의 개수를 출력하는 문제입니다. (백준에 없는 문제인것 같습니다. 검색해도 푼 사람이 없더라고요.) 저는 동적계획법을 이용해서 풀었습니다.def solve(L, S): dp &#61; [[0 for i in range(S)] for j in range(L)] for i in range(0,L): for j in range(0,S): if i &#61;&#61; 0 or j &#61;&#61; 0: dp[i][j] &#61; 1 else: for k in range(0,j&#43;1): dp[i][j] &#61; dp[i][j] &#43; dp[i-1][k] return dp[L-1][S-1] L, S &#61; [int(x) for x in input().split()] print(solve(L, S)%2147483647)자릿수의 합을 구하는 문제라서 저는 중복조합을 생각했고 동적계획법으로 낮은 수에서 합과 자릿수를 늘려가는 방식으로 문제를 풀었습니다. 제출이 안되는 이유가 무엇인지 모르겠는데 도와주실 분 계신가요?

다크 템플러 · Answer

동적 계획법을 사용하는데 반복문이 3중으로 돌아가면 거의 타임오버 납니다.보아하니 S를 일일이 다 체크할 필요는 없을 것 같아요.저는 각 자릿수를 하나씩 배정해가는 방식이 맞을 것 같습니다.무슨 뜻이나면 첫 번째 자릿수에 1~9를 다 박아보고, 각 케이스마다 L-1 자릿수의 경우의 수를 다시 구하는 거죠.중복을 DP로 처리하구요. ex) 19xxxx, 91xxxx일 때 xxxx의 개수는 같겠죠.

abccbama · Answer

코테한지 오래되었는데저라면 자릿수에 대한 합의 경우의수부터 구할거같아요합이 6이고 자릿수가 4이다 라고하면합이 6이 되는 경우는 1 1 2 2, 1 1 3 1, 4 1 1 , 3 2 1 0, 2 2 2 0, 5 1 0 0, 4 2 0 0, 3 3 0 0, 6 0 0 09개의 경우의 수가 나오는데 조합돌리면 개수가 나오겠죠 ... (0이 앞으로 오는 경우의수는 또 빼야겟네요)그런식으로 할거고소수 나머지 연산도 for문에 넣어줘야할 것 같아요 ㅎ언어가 파이썬같은데 숫자가 무한히 증가해도 괜찮으면 for문에 안넣어도 되겠지만요

자릿수의 합이 같은 자연수 개수 구하기

2개의 답변

Q&A 목록