다이나믹 프로그래밍48 [백준] 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. [백준] 22114: 창영이와 점프 - JAVA https://www.acmicpc.net/problem/22114 풀이뭔가 문제를 이해하는데 오래걸렸다... 컨디션 난조?? 아무튼.. n개의 블럭들 사이에 거리가 얼마나 떨어져있는지 n-1개의 숫자가 주어진다. `(블럭) 2 (블럭) 3 (블럭) 1 (블럭) 5 (블럭) 3 (블럭) 5 (블럭)` 이렇게 블럭이 위치하고있는것이다. 이차원 dp배열을 만들었다. [n][2] 사이즈로 만들어서 [i][0]의 경우 점프를 하지 않은 경우, [i][1]의 경우 점프를 한 경우이다. 다음 블럭까지 거리가 k보다 크다면 [i][1]에 [i-1][0]값에 1을 더해주고, [i][0]에는 점프를 하지 않았을 때 해당 블럭부터 시작한다는 의미로 1을 넣어준다. k보다 작다면 이전값에서 1씩 더해준다. 값을 더하면서 정.. 2024. 7. 1. [백준] 2228: 구간 나누기 - JAVA https://www.acmicpc.net/problem/2228 풀이n개의 수로 이루어진 배열에서 m개의 구간을 선택해 각 구간들의 합의 최댓값을 구하는 문제. 단, 구간 사이에는 최소 1의 간격이 있어야한다. dp 이차원 배열을 만들었다. `[수의 번호][구간의 개수]`로 구성했다.for (int k = i; k > 0; k--) { if (k - 2 >= 0) { dp[i][j] = Math.max(dp[i][j], dp[k - 2][j - 1] + sum[i] - sum[k - 1]); } else if (k == 1 && j == 1) { dp[i][j] = Math.max(dp[i][j], sum[i]); }} k번째 원소를 보면서 k번째 원소가 포함되.. 2024. 6. 27. [백준] 2688: 줄어들지 않아 - JAVA https://www.acmicpc.net/problem/2688 풀이줄어들지 않는 수는 그 숫자의 각 자리수보다 그 왼쪽 자리 수가 작거나 같다는 것을 말한다. 예를 들어, 1234, 0011, 2223 과 같은 숫자는 줄어들지 않는 수이다. 이 문제에서는 0000과 같이 숫자의 앞에 0이 있어도 숫자로 인정이 되는 문제였다. dp를 이용해 해결했다. 이차원 배열을 만드는데, ```long[][] dp = new long[max + 1][10];``` 으로 테스트케이스의 최댓값까지 1씩 늘려가면서, 0~9까지 10개의 숫자를 확인할 수 있게 하였다. 예를 들어, ```dp[2][8]```이 의미하는 바는 2자리 줄어들지 않는 수 중 8로 끝나는 수들의 개수를 의미한다. 1자리 숫자들을 모두 1로 초기화.. 2024. 6. 12. [백준] 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. [백준] 14863: 서울에서 경산까지 - JAVA https://www.acmicpc.net/problem/14863 풀이서울에서 경산까지 이동하는 과정에서 최대한 많은 금액을 벌기 위해 최적의 경로를 찾는 문제이다. DP를 통해 각 단계에서 걷기와 자전거로 이동할 수 있는 모든 경우를 고려하여 최대 금액을 구하는 방법을 사용했다. 각 단계에서 걷기와 자전거를 선택할 수 있다. 점화식은 다음과 같다. // 시간: walk[i][0], bike[i][0]// 금액: walk[i][1], bike[i][1]dp[i][t+walk[i][0]]=max(dp[i][t+walk[i][0]],dp[i−1][t]+walk[i][1])dp[i][t+bike[i][0]]=max(dp[i][t+bike[i][0]],dp[i−1][t]+bike[i][1]) 메모리: 57.. 2024. 6. 10. [백준] 11058: 크리보드 - JAVA https://www.acmicpc.net/problem/11058 풀이크리보드는 전체 선택, 복사, 붙여넣기, 출력 버튼이 있다. 버튼을 N번 눌러서 화면에 출력된 A개수를 최대로 하는 방법을 찾아야 한다. DP를 이용해 해결했다. DP배열을 초기화 후 DP배열을 채우면서 최적의 결과를 찾는다. for (int i = 1; i 6) { // 6번 이후부터는 복사&붙여넣기를 고려 for (int j = 3; j 메모리: 14204KB시간: 124ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 6. 10. [백준] 17953: 디저트 - JAVA https://www.acmicpc.net/problem/17953 풀이M종류의 디저트를 N일동안 하루에 하나씩 먹어야 한다. 전날 먹었던 것과 같은 것을 먹으면 만족감이 반으로 주는데, N일동안 최대의 만족감을 구해야 한다. 2차원 dp 배열을 만들었다. 각 날짜에 각 디저트마다 전날의 dp배열의 값들을 토대로 갱신해줬다. 전날과 같은 맛이라면 2로 나눠 더해줬다. 메모리: 92884KB시간: 552ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffered.. 2024. 5. 30. [백준] 16194: 카드 구매하기 2 - JAVA https://www.acmicpc.net/problem/16194 풀이카드팩들의 가격이 주어진다. 카드 i개가 포함된 카드팩의 가격은 Pi원이다. dp 배열을 최대값으로 초기화 해주고, 탐색을 진행했다.dp[0] + card[n]dp[1] + card[n - 1]...dp[n] + card[0] `dp[n]` 은 위 경우 중 최소가 되는 값이다. 메모리: 14528KB시간: 144ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new.. 2024. 5. 23. [백준] 1577: 도로의 개수 - JAVA https://www.acmicpc.net/problem/1577 풀이n x m 사이즈의 도시에서 (0, 0) 부터 (n, m)까지 가는 경우의 수를 구해야 한다. 다만, 공사중인 도로가 있어서 지나갈 수 없는 곳이 있다. `0 0 0 1` 과 같이 주어지는데 이는 (0, 0)에서 (0, 1)로 가는 도로를 이용할 수 없다는 것을 말한다. 3차원배열을 만들어서 가로 도로, 세로 도로의 공사 여부를 저장했다. 그 후, (0, 0)으로 부터 가로로만 갔을 때, 세로로만 갔을 때를 1로 채워주고 bottom-up방식으로 dp배열을 채워주었다. 메모리: 14312KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { pu.. 2024. 5. 23. 이전 1 2 3 4 5 다음