728x90 배낭 문제3 [JAVA]백준 14728번: 벼락치기 www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 1. 문제 설명 준석이가 공부할 수 있는 총시간의 개수와 공부해야 하는 단원의 개수가 주어진다. 단원마다 단원의 문제를 맞히기 위해 필요한 공부시간과 점수가 주어진다고 하였을 때 준석이가 얻을 수 있는 최대 점수를 구하는 문제이다. 2. 풀이 간단한 DP 문제이다. dp[x] = 공부할 수 있는 시간이 x일 때 준석이가 얻을 수 있는 최대 점수 시간 복잡도 O(NT).. 2021. 3. 18. [JAVA]백준 7579번: 앱 www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 1. 문제 설명 N개의 앱이 활성화되어있고 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있고, 앱 Ai를 비 활성하는 비용은 ci라고 하자. M 바이트 이상의 메모리를 추가로 확보하려고 할 때 비용 ci의 합의 최솟값을 구하는 문제이다. 2. 풀이 다이나믹 프로그래밍을 이용하여 풀 수 있다. cost[x] = 비용의 합이 X일 때, 추가로 확보할 수 있는 최대 메모리 = Math.min(cost [x], .. 2021. 3. 8. [JAVA]백준 18427번: 함께 블록 쌓기 www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 1. 문제 설명 N명의 학생들이 최대 M개의 블록을 가지고, 한 학생당 최대 1개의 블록만을 사용할 수 있을 때 (사용하지 않는 경우도 가능) 높이가 정확히 H인 탑을 만드는 경우의 수를 구하는 문제. 2. 풀이 dp를 이용해서 간단하게 풀 수 있는 문제이다. 1번부터 X 학생까지 높이 Y인 탑을 만들 수 있는 경우의 수를 dp [X][Y]라 하고, X학생이 가진 블록을 .. 2021. 2. 26. 이전 1 다음 728x90
