정수 n을 k개의 자연수로 분할하는 방법의 수

10772번: π-day n개의 파이를 k명의 사람에게 분배하는데 각 사람은 적어도 1개의 파이를 받고, 앞 사람보다 적게 받을 수는 없다 예를 들어 7개의 파이를 5명에게 분배할려면 1 1 1 1 3 1 1 1 2 2 는 유효하지만 2 1 1 2 1은 유효한 경우가 아니다 가능한 방법의 수는? -------------------------------------------------------------------------------------------------------------------------------------------- dp[i][j][x]를 i번째 사람에 j개 분배하고 남은 개수가 x개라고 할때 방법의 수라고 하면 O(N^4)에 해결할 수 있다 처음에 0번 사람에게 j개를 분배하..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 18.
• textsms

integer partition5 -최댓값이 제한된 상태에서 원소의 합이 n이 되는 방법의 수 구하기-

1. 문제 9599번: Equal Sum Sets (acmicpc.net) 9599번: Equal Sum Sets Let us consider sets of positive integers less than or equal to n. Note that all elements of a set are different. Also note that the order of elements doesn’t matter, that is, both {3, 5, 9} and {5, 9, 3} mean the same set. Specifying the number of set e www.acmicpc.net 2. 풀이 이번엔 집합의 원소 최댓값이 n이면서 k개의 서로 다른 정수를 사용하고 합이 s가 되는 방법의 수를 구..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 10. 27.
• textsms

integer partition4 -서로 다른 소수의 합으로 자연수를 만드는 방법의 수(역으로 순회하는 테크닉)-

1. 문제 3908번: 서로 다른 소수의 합 (acmicpc.net) 3908번: 서로 다른 소수의 합 양의 정수는 서로 다른 소수의 합으로 나타낼 수 있다. 두 정수 n과 k가 주어졌을 때, n을 서로 다른 k개의 소수의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 여기서 덧셈의 순 www.acmicpc.net 2. 풀이 소수만을 사용하는데, 서로 다른 소수를 사용해야하고 k개를 사용해서 합했을때 n을 만드는 방법의 수를 구하기 일단 도구로 소수를 구해야겠지 n이 최대 1120이니까 1120이하의 소수를 모두 에라토스테네스의 체로 구해놓고 def get_prime(n): result = [1]*(n+1) for i in range(2,int(((n+1)**(1/2)))+1): if res..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 10. 27.
• textsms