최솟값들로 배낭을 구성하고 이들 중 최댓값을 찾아야하는 특이한 배낭문제

2073번: 수도배관공사 길이가 L, 용량이 C인 파이프들이 주어질때, 이들을 적절히 선택하여 길이가 정확히 D가 되도록 한다 이때 수도관의 용량은 선택한 파이프들의 용량들 중 최솟값이 된다 그리고 길이는 선택한 파이프들의 길이의 총합이다. 이때, 가능한 수도관 용량들 중 최댓값을 구한다 ------------------------------------------------------------------------------------------------------------------------------------ 단순한 배낭 문제라고 생각해서 from sys import stdind,p = map(int,stdin.readline().split())A = []for _ in range(p): ..

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

정수 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

구간을 잡아야하는 matrix chain multiplication 다이나믹 프로그래밍

11049번: 행렬 곱셈 순서  n*m인 행렬과 m*k인 행렬을 곱하면 n*k인 행렬이 나오고 연산량은 n*m*k이다 A의 크기가 5*3, B의 크기가 3*2, C의 크기가 2*6인 경우 ABC를 곱할때 (AB)C를 곱하면 AB를 곱해서 5*3*2번, AB는 5*2행렬이고, AB와 C를 곱해서 5*2*6 = 총 90번 A(BC)를 곱하면 BC를 곱해서 3*2*6번, BC는 3*6행렬이고 A와 BC를 곱해서 5*3*6 = 총 126번 행렬의 크기 r*c가 n개 주어진다. 이 n개의 행렬은 곱할 수 있다고 할때, 최소 연산량을 구한다면? ------------------------------------------------------------------------------------------------..

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

안겹치게 구간을 나누는 다이나믹 프로그래밍 테크닉

문제1. 11985번: 오렌지 출하  n개의 오렌지가 1번부터 n번까지 순서대로 있는데, 순서대로 앞에서부터 상자에 나눠서 넣는다 이때 한 상자에 넣는 오렌지는 번호가 연속해야한다 한 상자당 최대 m개까지 오렌지를 넣을 수 있다 이때 상자를 포장하는 비용은 K + s*(a-b)로 s는 상자에 넣는 오렌지의 개수이고 a는 오렌지 크기의 최댓값, b는 최솟값이다 이때 모든 오렌지를 포함하는 비용의 최솟값은? ------------------------------------------------------------------------------------------------------------------------- dp[i] = i번째 오렌지까지 포장하는데 드는 비용의 최솟값 i = 0인 경우 dp[..

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

출발 조건이 까다로운 2차원 배열 목적지까지 이동하는 다이나믹 프로그래밍

14722번: 우유 도시 (0,0)에서 (n-1,n-1)까지 이동하면서 우유를 마시는데 맨 처음에는 딸기우유를 마신다 딸기우유를 마신 다음에 초코우유를 마신다 초코우유를 마신 다음에 바나나 우유를 마신다 바나나 우유를 마신 다음에 딸기 우유를 마신다 위 4가지 조건을 만족하면서 우유를 마시는데, (x,y)에는 딸기, 초코, 바나나 우유 셋 중 하나만 있다.  최대로 마실 수 있는 우유 개수는? ------------------------------------------------------------------------------------------------------------------------------------------------------ dp[i][j][k] = (j,i)에 있는데 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 1. 27.
• textsms

무게가 실수 float인 배낭 문제에 필요한 테크닉

4781번: 사탕 가게  가지고 있는 돈이 있고 사탕의 가격과 칼로리가 주어질때, 주어진 돈으로 얻을 수 있는 최대 칼로리를 구하는 문제 각 사탕은 중복해서 구매할 수 있다 무한 배낭 문제인데 특이한 점은 무게가 소수점 둘째자리까지 주어진다는 점 배낭 문제로 해결하고 싶어도 배열의 크기는 실수로 만들수 없다 그러면 어떻게 해야할까? 소수점 둘째자리까지 주어지기 때문에, 실수인 가격을 모두 100을 곱해서 정수로 만들면 모두 동등하게 100을 곱했기 때문에 아무 문제가 없다 그리고 무한 배낭 문제이기 때문에 무게를 순회할때는 정방향으로 순회하도록 for i in range(p,m+1): 이렇게 from sys import stdinwhile 1: n,m = stdin.readline().rstrip(..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 1. 4.
• textsms