양팔저울을 이용해서 무게를 알아낼 수 있는 추를 찾는 방법

2629번: 양팔저울 양팔저울에 1g과 4g의 추를 이용해서, 어떤 구슬이 3g인지 확인할려면 한쪽에 1g의 추, 3g의 구슬을 놓고 다른 한쪽에는 4g의 추를 올려놓은 다음 양쪽이 균형을 이루는지 확인하면 된다 가지고 있는 추와 무게를 확인하려는 구슬이 주어질때 무게를 확인이 가능한 구슬을 모두 찾는다 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 핵심은 한쪽에 추를 올리는 것이 +라고 한다면 반대쪽에 올리는 것은 -라고 생각하는 것이다 한쪽에 +4g을 올리면 다른 한쪽에 ..

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

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

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

무게가 실수 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

정확히 배낭의 크기만큼 담아야하는 독특한 배낭 문제

13910번: 개업 (acmicpc.net) n그릇의 요리를 해야하는데 가지고 있는 도구 크기들이 주어질때,  주어진 도구를 사용할때는 정확히 해당 크기만큼 요리해야한다면 n그릇을 만들기 위해 최소 몇번 요리해야하는지 예를 들어 1그릇, 3그릇용 도구가 주어지면 3그릇용 도구로 2그릇을 요리하지는 않고,  1그릇용 도구만 사용하여 1그릇만 요리할 수도 있고 1그릇, 3그릇 도구를 동시에 써서 4그릇을 요리할 수도 있다 또한 4그릇을 만들어야할때, 5그릇을 만들지 않는다  배낭문제처럼 dp[i] = i그릇 요리를 만들기 위해 해야하는 최소 요리 수 0그릇 요리에는 당연히 0번이면 되니까 dp[0] = 0 i = 1,2,3,...,n에 대하여 j번째 도구를 사용할때, k = j+1,j+2,...,m-1번째 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 10. 1.
• textsms

index와 value를 바꾸는 다이나믹 프로그래밍 트릭

E - Maximum Glutton (atcoder.jp) E - Maximum GluttonAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 단맛이 a 짠맛이 b로 주어지는 n개의 음식을 먹는데  단맛이 x를 초과하거나 짠맛이 y를 초과하는 순간 음식을 그만 먹는다면 음식을 최대한 많이 먹고자할때, 최대로 먹을 수 있는 음식의 수는? 전형적인 배낭 문제라서 dp[i][j][k] = i번째 음식까지 먹었을때 단맛의 합이 j, 짠맛의 합이 k인 경우 먹은 최대 음식의 수로  하면 될것 같다고 생각을 했는데 n이 80이고 a가 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 7. 29.
• textsms