알고리즘/백준
[JAVA] 백준 dp 부수기
fladi
2025. 5. 17. 18:01
728x90
9251 LCS - 골드5
https://www.acmicpc.net/problem/9251
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String a = br.readLine();
String b = br.readLine();
int[][] dp = new int[a.length()+1][b.length()+1];
for (int i =0; i<a.length(); i++) {
char c1 = a.charAt(i);
int idx1 = i+1;
for (int j =0; j<b.length(); j++) {
char c2 = b.charAt(j);
int idx2 = j+1;
if (c1 == c2) {
dp[idx1][idx2] = Math.max(dp[idx1][idx2], dp[idx1-1][idx2-1]+1);
} else {
dp[idx1][idx2] = Math.max(dp[idx1-1][idx2], dp[idx1][idx2-1]);
}
}
}
System.out.println(dp[a.length()][b.length()]);
}유명한 LCS문제다. 점화식만 알고있다면 어렵지 않다.
17404 RGB거리 2 - 골드4
https://www.acmicpc.net/problem/17404
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int houseCnt = Integer.parseInt(br.readLine());
int[][] cost = new int[houseCnt][3];
int[][][] dp = new int[3][2][3]; //[첫번째 무슨색 채울건지][house 인덱스 % 2 값][rgb]
//(0)입력받기
for (int i = 0; i < houseCnt; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
cost[i][j] = Integer.parseInt(st.nextToken());
}
}
//(1)초기화 작업
for (int i =0; i<3; i++) {
for (int j =0; j<2; j++) {
Arrays.fill(dp[i][j], 1000000);
}
}
dp[0][0][0] = cost[0][0];
dp[1][0][1] = cost[0][1];
dp[2][0][2] = cost[0][2];
//(2)dp배열 갱신
for (int i =1; i<houseCnt; i++) {
int currentIdx = i % 2;
int prevIdx = (i+1) % 2;
for (int j=0; j<3; j++) {
dp[j][currentIdx][0] = Math.min(dp[j][prevIdx][1] + cost[i][0], dp[j][prevIdx][2] + cost[i][0]);
dp[j][currentIdx][1] = Math.min(dp[j][prevIdx][0] + cost[i][1], dp[j][prevIdx][2] + cost[i][1]);
dp[j][currentIdx][2] = Math.min(dp[j][prevIdx][0] + cost[i][2], dp[j][prevIdx][1] + cost[i][2]);
}
}
//(3)최솟값 구하기
int currentIdx = (houseCnt-1) % 2;
int result = Integer.MAX_VALUE;
result = Math.min(result, dp[0][currentIdx][1]);
result = Math.min(result, dp[0][currentIdx][2]);
result = Math.min(result, dp[1][currentIdx][0]);
result = Math.min(result, dp[1][currentIdx][2]);
result = Math.min(result, dp[2][currentIdx][0]);
result = Math.min(result, dp[2][currentIdx][1]);
System.out.println(result);
}
}
3차원 dp 배열로 해결했다. dp배열의 각 요소는 다음과 같음
- [3]: 빨강/초록/파랑 집으로 시작하는 경우
- [2]: 집의 인덱스를 %2 한 값 (모든 dp값을 저장할 필요가 없기 때문에 2개로 했다)
- [3]: (1~N)까지 채우고 현재 집을 칠한 색(RGB중 하나)
1106 호텔 - 골드4
https://www.acmicpc.net/problem/1106
느낌은 배낭문제와 굉장히 유사했다. 풀이는 크게 2가지 방법이 있다.
- 특정 비용으로 늘릴 수 있는 최대 고객 수 구하기
- 특정 고객 수를 위한 최소 비용 구하기
문제에 정확히 C명이 아니라 "적어도 C명"이라고 되어있기 때문에 C보다 높은 가장 최소 비용을 구해야한다. 그래서 1번과 2번방법 모두 column 범위를 크게 잡아줘야한다는 걸 알 수 있었다. 가장 처음에는 1번 방식으로 풀어봤다.
1106 - 1번 방식 풀이
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int requiredCnt = Integer.parseInt(st.nextToken()); // x <= 1000
int cityCnt = Integer.parseInt(st.nextToken()); // x <= 20
int[][] dp = new int[2][requiredCnt * 100 + 1]; //특정 비용으로 늘릴 수 있는 최대 고객 수 구하기
for (int i =0; i<cityCnt; i++) {
st = new StringTokenizer(br.readLine());
int cost = Integer.parseInt(st.nextToken());
int customerCnt = Integer.parseInt(st.nextToken());
int current = i % 2;
int prev = (i + 1) % 2;
for (int j=0; j<dp[0].length; j++) {
if (dp[current][j] < dp[prev][j])
dp[current][j] = dp[prev][j];
if (j < cost) {
continue;
}
dp[current][j] = Math.max(dp[current][j], dp[current][j-cost] + customerCnt);
}
}
//C명 이상이 되는 비용을 찾으면 break => 최소비용
int tmp = (cityCnt-1) % 2;
for (int i =0; i<dp[0].length; i++) {
if (dp[tmp][i] >= requiredCnt) {
System.out.println(i);
break;
}
}
}- requiredCnt를 만들기 위해 사용해야할 최대 금액은 100 * requiredCnt이다. ("비용은 100 이하, 얻을 수 있는 고객수는 자연수"라고 문제에 명시되어 있다) 이 값을 column 크기로 지정하여 특정 비용으로 얻을 수 있는 최대 고객수를 dp배열에 저장했다.
- row는 2개만 사용하여 아껴썼다.
- requiredCnt 이상을 얻을 수 있는 비용을 for 루프로 찾아서 바로 반환하면 답을 구할 수 있다. 금액 범위는 넉넉하게 잡아줬기 때문에 무조건 답은 출력된다.
1106 - 2번 방식 풀이
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int requiredCnt = Integer.parseInt(st.nextToken()); // x <= 1000
int cityCnt = Integer.parseInt(st.nextToken()); // x <= 20
int[][] dp = new int[2][requiredCnt+101]; //특정 고객수를 만들기 위한 최소 비용
Arrays.fill(dp[0], 100_001);
Arrays.fill(dp[1], 100_001);
dp[0][0] = 0;
dp[1][0] = 0;
for (int i =0; i<cityCnt; i++) {
st = new StringTokenizer(br.readLine());
int cost = Integer.parseInt(st.nextToken());
int customerCnt = Integer.parseInt(st.nextToken());
int current = i % 2;
int prev = (i + 1) % 2;
for (int j=0; j<dp[0].length; j++) {
if (dp[current][j] > dp[prev][j])
dp[current][j] = dp[prev][j];
if (j < customerCnt) {
continue;
}
dp[current][j] = Math.min(dp[current][j], dp[current][j-customerCnt] + cost);
}
}
int tmp = (cityCnt-1) % 2;
int min = Integer.MAX_VALUE;
for (int i =requiredCnt; i<dp[0].length; i++) {
if (dp[tmp][i] < min) {
min = dp[tmp][i];
}
}
System.out.println(min);
}- dp로 갱신해야할 고객 수 범위는 requiredCnt + 100이다. "적어도 C명 이상"이라고 명시되어 있기 때문에, "정확히 C명"인 비용보다 "C명보다 큰 고객수"일 때 비용이 더 낮을 수도 있다. 비용의 범위는 100이하이기 때문에 크기는 최대 requiredCnt+100밖에 되지 않는다.
- 위 방식과 마찬가지로 row는 2개만 사용하여 아껴썼다.
- "정확히 C명"일 때의 비용부터 "C명보다 큰 고객수"일 때의 비용을 모두 비교하여 최솟값을 min에 넣어주고 출력해주면 답이 나온다.
column 범위가 1번이 훨씬 크기 때문에 계산 횟수도 더 많다. 그래서 2번이 성능이 더 좋게 나오는 걸 확인할 수 있었다.
1958 LCS3 - 골드4
https://www.acmicpc.net/problem/1958
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String a = br.readLine();
String b = br.readLine();
String c = br.readLine();
int[][][] dp = new int[a.length()+1][b.length()+1][c.length()+1];
for (int i =0; i<a.length(); i++) {
char c1 = a.charAt(i);
int idx1 = i+1;
for (int j =0; j<b.length(); j++) {
char c2 = b.charAt(j);
int idx2 = j+1;
for (int r=0; r<c.length(); r++) {
char c3 = c.charAt(r);
int idx3 = r+1;
//모두 같으면
if (c1 == c2 && c2 == c3) {
dp[idx1][idx2][idx3] = dp[idx1-1][idx2-1][idx3-1] + 1;
} else {
//idx1은 고정이라고 생각하기
dp[idx1][idx2][idx3] = Math.max(dp[idx1][idx2-1][idx3], dp[idx1][idx2][idx3-1]);
dp[idx1][idx2][idx3] = Math.max(dp[idx1][idx2][idx3], dp[idx1-1][idx2][idx3]);
}
}
}
}
System.out.println(dp[a.length()][b.length()][c.length()]);
}3차원 dp를 써야할 것 같다는 느낌이 왔다. 3가지 글자를 동시에 비교하고 갱신해야한다는 점만 고려하면 2차원 LCS와 유사하게 풀이할 수 있었다.
2133 타일 채우기 - 골드4
https://www.acmicpc.net/problem/2133
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
if (n % 2 == 1) {
System.out.println(0);
return;
}
int[] dp = new int[n+1];
dp[0] = 1;
//1. ||_ 3x2
//2. _|| 3x2
//3. =_ 3x2
//4. __ |=| 3x4 3x6 3x8 ...
//5. |=| __ 3x4 3x6 3x8 ...
for (int i =2; i<dp.length; i+=2) {
dp[i] = dp[i-2] * 3;
if (i >3) {
int tmp = 2;
while (i - tmp*2 >= 0) {
dp[i] += 2*dp[i - tmp*2];
tmp++;
}
}
}
System.out.println(dp[dp.length-1]);
}처음엔 막막할 수 있지만, 나올 수 있는 경우가 한정적이라는 걸 알고나면 굉장히 쉬워지는 문제다. 나올 수 있는 경우의 수는 아래의 5가지 경우가 끝이다.
나눠보면 5가지가 나오고, 마지막 2개는 +2개씩 무한하게 늘어날 수 있다.
123번째로 dp배열 경우의 수를 채워주고, 45번째를 while문으로 더해주면 답이 금방 나온다.
+) 홀수인 경우는 구할 수 없기 때문에 0을 반환해주면 된다
2631 줄 세우기 - 골드4
https://www.acmicpc.net/problem/2631
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = Integer.parseInt(br.readLine());
int[] arr= new int[cnt];
int[] dp = new int[cnt];
for (int i = 0; i < cnt; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int max = 0;
for (int i =0; i<cnt;i++) {
dp[i] = 0;
for (int j =0; j<i; j++) {
if (arr[j] < arr[i]) {
if (dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
max = Math.max(dp[i], max);
}
}
}
}
System.out.println(cnt - max);
}(문제가 굉장히 귀여워서 마음에 든다)
LIS라는 생각도 못했는데, LIS였다. 최장 증가 수열 개수를 찾아내서 고정시키고 나머지 애기들만 옮겨주면 최소 횟수로 옮길 수 있다.
1516 게임 개발 - 골드3
https://www.acmicpc.net/problem/1516
class Node implements Comparable<Node> {
int id;
int cost;
public Node(int id, int cost) {
this.id = id;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.cost, o.cost);
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int typeCnt = Integer.parseInt(br.readLine());
List<Integer>[] relation = new ArrayList[typeCnt];
List<Integer>[] dependsOn = new ArrayList[typeCnt];
for (int i =0; i<typeCnt; i++) {
relation[i] = new ArrayList<>();
dependsOn[i] = new ArrayList<>();
}
boolean[] clear = new boolean[typeCnt];
int[] times = new int[typeCnt];
for (int i = 0; i < typeCnt; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
//건축 시간 추가
int time = Integer.parseInt(st.nextToken());
times[i] = time;
while (true) {
int value = Integer.parseInt(st.nextToken());
if (value == -1) {
break;
}
dependsOn[i].add(value-1);
relation[value-1].add(i);
}
}
int[] minTime = new int[typeCnt];
Arrays.fill(minTime, Integer.MAX_VALUE);
Queue<Node> queue = new PriorityQueue<>();
for (int i = 0; i < typeCnt; i++) {
if (dependsOn[i].isEmpty()) {
queue.add(new Node(i, times[i]));
minTime[i] = times[i];
}
}
//dijkstra
while (!queue.isEmpty()) {
Node poll = queue.poll();
if (poll.cost > minTime[poll.id]) {
continue;
}
clear[poll.id] = true;
for (int near: relation[poll.id]) {
//다 안지어졌으면 ㄴㄴ
boolean canStart = true;
int maxTime = times[poll.id];
for (int mom: dependsOn[near]) {
if (!clear[mom]) {
canStart = false;
break;
}
maxTime = Math.max(maxTime, minTime[mom]);
}
if (!canStart) {
continue;
}
if (minTime[near] > maxTime + times[near]) {
minTime[near] = maxTime + times[near];
queue.add(new Node(near, times[near]));
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < typeCnt; i++) {
sb.append(minTime[i]).append("\n");
}
System.out.print(sb);
}
}다익스트라로 풀릴 것 같아 해봤더니 풀렸다.
나는 queue에 넣을 때, 의존하는 건물이 모두 세워진 건물만 queue에 넣어주도록 했다.
+) 이 때 (의존하는 건물들 중 세워진 시간이 가장 큰 건물의 지은 시간 + 현재 건물이 지어지는 시간)이 현재 건물이 지어지는 시간이라는 걸 유의해야한다.
이 문제는 위상정렬로도 풀 수 있다고 한다. 위상정렬이 기억나지 않아서.. 위상정렬로 푼 블로그를 첨부하겠다.
https://steady-coding.tistory.com/86
2342 Dance Dance Revolution - 골드3
https://www.acmicpc.net/problem/2342
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[][][] dp = new int[100_001][5][5]; //넉넉하게 최댓 값으로 초기화
StringTokenizer st = new StringTokenizer(br.readLine());
int idx = 0;
int last = 0; //마지막 발자취 저장
//두 발 모두 0에서 시작
for (int i = 0; i < 5; i++) {
Arrays.fill(dp[0][i], 400001);
}
dp[0][0][0] = 0;
while (true) {
int value = Integer.parseInt(st.nextToken());
if (value == 0) {
break; //입력 끝
}
int current = ++idx;
//초기화
for (int i = 0; i < 5; i++) {
Arrays.fill(dp[current][i], 400001);
}
//dp하기 - value를 밟기위한 모든 경우 계산
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
int strength = getStrength(j, value);
dp[current][i][value] = Math.min(dp[current][i][value], dp[current - 1][i][j] + strength);
dp[current][value][i] = Math.min(dp[current][value][i], dp[current - 1][j][i] + strength);
}
}
last = value;
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < 5; i++) {
min = Math.min(min, dp[idx][i][last]);
min = Math.min(min, dp[idx][last][i]);
}
System.out.println(min);
}
private static int getStrength(int a, int b) {
if (a == b) {
return 1;
}
if (a == 0) {
return 2;
}
if (Math.abs(a - b) == 2) {
return 4;
}
return 3;
}
}dp는 3차원 배열을 사용해줬다. 각각은 다음을 의미한다
[ㅇ][][]: 밟아야하는 발판의 인덱스
[][ㅇ][]: 왼발 위치
[][][ㅇ]: 오른발 위치
특정 step을 밟을 때 초기화해주는 로직은 다음과 같다.
ex) 4를 밟아야하는 상황
- 오른발로 4를 밟기: dp[current][i][4] = Math.min(dp[current][i][4], dp[current-1][i][j] + 발옮기기비용)
- 왼발로 4를 밟기: dp[current][4][i] = Math.min(dp[current][4][i], dp[current-1][j][i] + 발옮기기비용)
여기서 i와 j는 0~4까지 이중루프로 돈다. 그냥 모든 발 위치인 경우를 다 고려해서 dp배열을 갱신한다고 보면된다.
발을 옮기는 비용은 메서드로 따로 빼줬다. 문제에 명시되어있는 그대로 구현해주면 된다.
728x90