다이나믹 프로그래밍을 이용한 partition minimum sum of difference of two subset(합의 차이가 최소가 되는 분할) 문제 해법

1. 문제 배열 A가 주어질때, A를 2개의 부분집합으로 분할하고자 하는데, 각 부분집합의 원소의 합이 X,Y이면 abs(X-Y)가 최소가 되도록 분할하고자 한다 이때, 그 최솟값을 구하거나 X,Y를 구하는 문제 A의 원소의 합이 total = sum(A)라면, 두 부분집합의 원소 합의 차이가 최소가 되는 것은 정확히 절반이 되는 경우이다. 그러니까 최대 target = total//2에 도달하는게 가장 좋다. 1) dp[i] = A의 원소를 일부 골라서 합했을때, i가 될 수 있는가? 만약 i-w를 만들 수 있다면, w를 더하면 i가 될 수 있으므로 dp[i-w] = 1이면 dp[i] = 1이 된다. #dp[i] = 배열 v의 원소를 일부 골라 합해서 i를 만들 수 있는가?target = total//..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2024. 7. 8.
• 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

integer partition 문제 3 - 서로 다른 자연수를 사용해서 특정한 자연수 n을 만드는 방법의 수는 홀수만을 사용해서 만드는 방법의 수와 같다(count number of partition of n)

1. 문제 9764번: 서로 다른 자연수의 합 (acmicpc.net) 9764번: 서로 다른 자연수의 합 첫째 줄에, 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. www.acmicpc.net 2. 풀이 dp[j][i]를 1부터 i까지의 자연수 중에서 최대 하나씩만 사용해서 j를 만드는 방법의 수라고 정의하자. 여기서 구성이 같은데 순서가 달라도 같은 방법으로 취급한다 https://deepdata.tistory.com/951 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2023. 10. 23.
• textsms