다이나믹 프로그래밍48 [백준] 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. [백준] 2624: 동전 바꿔주기 - JAVA https://www.acmicpc.net/problem/2624 풀이dp문제. 동전으로 특정 금액을 만드는 문제였는데 동전의 개수가 정해져있어서 어려웠다. 동전 금액과 각각의 개수가 주어지는데 동전들을 이용해서 T원을 만들어야 한다. 금액에 대해 동전 몇 개를 썼을 때 경우의 수를 저장하는 dp배열을 만들었다. 동전 * 개수를 price라고 하면 점화식은 다음과 같다. `dp[k][i + 1] += dp[k - price][i];`dp[k][i+1]은 동전 (i+1)개를 썼을 때 k의 금액을 만들 수 있는 경우의 수이다. 메모리: 18072KB시간: 164ms언어: Java 11import java.io.*;import java.util.*;public class Main { public sta.. 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. [백준] 3359: 사각 사각 - JAVA https://www.acmicpc.net/problem/3359 풀이DP문제이다. 사각형을 각각 가로로 놓을지 세로로 놓을지 정해서 위쪽 둘레의 최댓값을 찾는다. dp배열을 이차원배열로 만들어 현재 사각형을 가로로 놓는다면 [0]에, 세로로 놓는다면 [1]에 값을 넣는다. 옆면까지 생각해야한다. 이전 dp배열에서 선택안한 변과 현재 선택안한 변의 차이를 더해 최댓값을 현재 dp배열에 더해준다. 메모리: 14480KB시간: 140ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader b.. 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. [백준] 25049: 뮤직 플레이리스트 - JAVA https://www.acmicpc.net/problem/25049 풀이dp문제. 처음부터 끝까지 한 번은 들어야 하므로 전체 수열의 값을 입력받으면서 더해준다. 앞으로 가면서 최대 부분합을 구해주고, 역방향으로 최대 부분합을 구해준다. [0 ~ i], [i + 1 ~ N - 1] 두 구간으로 나누어 i의 경우를 계산하여 최대값을 구하여 더해준다. - 참고: Kadane's Alogorithm 메모리: 81920KB시간: 824ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br.. 2024. 5. 11. [백준] 28017: 게임을 클리어하자 - JAVA https://www.acmicpc.net/problem/28017 풀이dp문제이다. 이전 회차의 무기 선택이 현재 회차의 선택에 영향을 미친다. 이전 회차까지의 최솟값을 구해놓고 최솟값에 현재 회차의 선택을 더해준다. 현재 선택한 무기가 이전 회차에서 선택한 무기와 같다면 그 다음 최솟값을 구하여 더해준다. 메모리: 36792KB시간: 652ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syst.. 2024. 5. 11. [백준] 20869: 김밥천국의 계단 - JAVA https://www.acmicpc.net/problem/28069 풀이bfs와 dp로 접근할 수 있는 문제. bfs메모리: 57612KB시간: 204ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.n.. 2024. 5. 11. 이전 1 2 3 4 5 다음