[백준, 파이썬] 1937 사전

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

1256번: 사전

개인적으로 사고 과정이 복잡하고 더러..운..? 문제였던것 같습니다.. 

우선 코드만 첨부하고 설명은 다음에 업로드하도록 하겠습니다.

이 문제는 메모리 용량과 시간을 잘보고 구현해야 하는데요.. 저는 이차원배열로 모든 조합 경우의 수를 

규칙에 따라 미리 저장하고 문제를 해결하였는데, 메모리 용량 초과로 결국 combination과 factorial함수를 다시 따로 구현해야 했습니다..  

 

n, m, k = list(map(int, input().split(' '))) N = n+m dp = [1] * (N+1) def factorial(N): if N==1 or N==0: dp[N] = 1 return 1; else: val = N * factorial(N-1); dp[N] = val return val def binomial(n1, n2, facto): return (facto[n1+n2]) / (facto[n1] * facto[n2]) def find_k(n, m, k, string, facto): if n==0: for _ in range(m): string.append('z') elif m==0: for _ in range(n): string.append('a') else: case = binomial(n-1, m, facto) if case < k: string.append('z') find_k(n, m-1, k-case, string, facto) elif case >= k: string.append('a') find_k(n-1, m, k, string, facto) return string factorial(N) answer_string = [] string = find_k(n, m, k, answer_string, dp) if k > binomial(n, m, dp): print(-1) else: for i in range(len(string)): print(string[i], end='')