배낭 문제8 [백준] 17845: 수강 과목 - JAVA https://www.acmicpc.net/problem/17845 풀이과목들의 공부시간과 중요도가 주어진다. 자신의 한계 공부 시간을 넘지 않으면서 중요도의 합이 최대가 되도록 과목들을 선택해야 한다. 문제를 보자마자 배낭 문제라고 떠올랐다. 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 무게의 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 하는 배낭 문제에서 말만 바꾼 문제였다. 과목들의 정보를 배열에 담고, 최대 n의 시간에 맞춰 과목들을 dp배열에 담았다. 메모리: memoryKB시간: speedms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] .. 2024. 7. 18. [백준] 17208: 카우버거 알바생 - JAVA https://www.acmicpc.net/problem/17208 풀이버거와 감자튀김을 조합하여 최대한 많은 주문을 처리하는 것이 목표이다. dp를 사용하여 해결했다. 주문을 처리하는 동안 남은 버거와 감튀의 수량을 고려하여 최대 주문 수량을 계산하는 배낭문제였다. 현재 주문을 포함하지 않는 경우 ``` dp[i][j][k] = dp[i - 1][j][k]```, 현재 주문을 포함하는 경우 ``` dp[i][j][k] = dp[i - 1][j - order[i][0]][k - order[i][1]] + 1``` 와 같은 점화식으로 처리했다. 메모리: 52300KB시간: 232ms언어: Java 11import java.io.*;import java.util.*;public class Main { .. 2024. 6. 10. [백준] 18427: 함께 블록 쌓기 - JAVA https://www.acmicpc.net/problem/18427 풀이N명의 학생이 들고있는 블럭을 인 당 최대 한 개 사용하여 높이 H를 정확하게 맞출 수 있는 경우의 수를 구해야한다. dp배열을 2차원으로 만들었다. `new int[n + 1][h + 1]` 1번 학생부터 시작하여 1~h까지 높이에 대해 경우의 수를 구한다. n번 학생이 특정 높이 h에 대해 만들 수 있는 경우의 수는 다음과 같이 구할 수 있다. `(n번 학생이 들고 있는 h 높이의 블록의 수) + (n-1번 학생까지 했을 때 h 높이를 만든 경우의 수) + (n번 학생이 가진 a 높이의 블록 + n-1번 학생까지 했을 때 h-a 높이를 만든 경우의 수)` 이 방법을 코드로 옮기면 다음과 같다.for (int i = 1; i = h.. 2024. 5. 19. [백준] 15817: 배수 공사 - JAVA https://www.acmicpc.net/problem/15817 풀이파이프의 길이와 각 길이 파이프들의 개수가 주어진다. 이 파이프들을 갖고 x길이를 만드는 문제이다. 길이가 짧은것부터 주어지므로 따로 정렬할 필요는 없었다. 길이가 짧은 파이프부터 보면서 x부터 0으로 내려가면서 역순 탐색을 통해 dp배열에 값을 누적시켰다. 메모리: 14324KB시간: 232ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Pipe { int length; int count; public Pipe(int length, int count) { this.leng.. 2024. 5. 17. [백준] 20303: 할로윈의 양아치 - JAVA https://www.acmicpc.net/problem/20303 풀이dp와 분리집합을 이용하는 문제. 사탕을 최대로 뺏어야 하는 문제였다. 친구들로부터 사탕을 뺏는데, K명 미만으로부터 사탕을 빼앗아야 한다. 한 친구의 사탕을 뺏으면 그와 친구인 친구들의 사탕을 함께 뺏는다. 각 친구별로 사탕의 개수를 알고 있고, 누구와 친구 관계를 갖고있는지 주어진다. 따라서, 분리집합(union-find)을 이용해 친구별로 그룹을 만들어 그룹별로 몇 명인지 몇 개의 사탕을 가지고 있는지 저장한다. 저장된 자료를 통해 배낭문제 알고리즘을 적용하여 최대 K-1명일 때 최댓값을 구했다. 메모리: 875636KB시간: 1152ms언어: Java 11import java.io.*;import java.util.*;pub.. 2024. 5. 12. [백준] 1535: 안녕 - JAVA https://www.acmicpc.net/problem/1535 풀이DP, 배낭 문제. 인사를 할때마다 체력을 잃고 기쁨을 얻는다. 체력 100에서 시작해서 0이 되면 죽는다. dp배열을 dp[사람의 수][100] 으로 설정했다. 사람마다 잃는 체력, 얻는 기쁨을 통해 이전 dp배열과 비교해준다. 점화식은 다음과 같다.dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - L[i]] + J[i]); 메모리: 14196KB시간: 176ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 5. 12. [백준] 28071: 승형이의 사탕 사기 - JAVA https://www.acmicpc.net/problem/28071 풀이dp문제이다. M개의 사탕 상자를 가져갈 수 있고, 사탕 개수의 총 합은 K로 나누어 떨어져야 한다. 상자의 개수와 나머지에 따라 dp배열을 생성한다. dp[i][j]에서 i를 상자의 개수, j를 나머지라고 하면 dp[i][j]의 값은 i-1개의 상자에서 "j - 현재 사탕상자의 사탕 개수"일때의 dp값을 이용하여 갱신한다. "j - 현재 사탕상자의 사탕 개수"가 음수가 되면 안되기 때문에 Math.floorMod연산을 사용했다. dp배열을 채운 후 나머지가 0인 경우 중 최댓값을 구한다. 메모리: 15152KB시간: 424ms언어: Java 11import java.io.*;import java.util.*;public class.. 2024. 5. 11. [백준] 1106: 호텔 - JAVA https://www.acmicpc.net/problem/1106 풀이dp문제. 고객수를 C명 늘려야 한다. 한 도시에서 한번의 비용으로 얻을 수 있는 고객의 수는 100이하이므로 C + 101 까지 dp배열을 만든다. 한 비용으로 얻을 수 있는 고객의 수를 value라고 할 때, "dp[j - value] + 비용"과 "dp[j]"의 최솟값을 dp[j]에 담는다. dp배열을 다 채운 후 인덱스가 C이상인 값들 중에서 최솟값을 찾는다. 메모리: 14224KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 5. 11. 이전 1 다음