DP
1. 계단 오르기
package com.codingtest.Algorithm.Chapter10.DP;
import java.util.Scanner;
public class 계단오르기 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int stairs = in.nextInt();
System.out.println(cntNum(stairs));
}
private static int cntNum(int stair) {
if (stair == 1 || stair == 0) {
return 1;
}
return cntNum(stair - 1) + cntNum(stair - 2);
}
}
2. 돌다리 건너기
package com.codingtest.Algorithm.Chapter10.DP;
import java.util.Scanner;
public class 돌다리_건너기 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int stairs = in.nextInt();
System.out.println(cntNum(stairs + 1));
}
private static int cntNum(int stair) {
if (stair == 1 || stair == 0) {
return 1;
}
return cntNum(stair - 1) + cntNum(stair - 2);
}
}
3. 최대 부분 증가 수열
package com.codingtest.Algorithm.Chapter10.DP;
import java.util.Arrays;
import java.util.Scanner;
public class 최대_부분_증가수열 {
public static int[] dy;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len = Integer.parseInt(in.nextLine());
String s = in.nextLine();
String[] strArr = s.split(" ");
int answer = 0;
int[] arr = Arrays.stream(strArr)
.mapToInt(Integer::parseInt)
.toArray();
dy = new int[arr.length];
dy[0] = 1;
for (int i = 1; i < arr.length; i++) {
int max = 0;
for (int j = i - 1; j >= 0; j--) {
if (arr[j] < arr[i] && dy[j] > max) {
max = dy[j];
}
}
dy[i] = max + 1;
answer = Math.max(answer, dy[i]);
}
System.out.println(answer);
}
}
실수한 부분
s = s.replaceAll(" ", "");
int[] arr = Arrays.stream(s.split(""))
.mapToInt(Integer::parseInt)
.toArray();
4. 가장 높은 탑 쌓기
package com.codingtest.Algorithm.Chapter3.DP;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class 가장_높은_탑_쌓기 {
static int[] dy;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
ArrayList<Brick> arr = new ArrayList<>();
dy = new int[num];
for (int i = 0; i < num; i++) {
int s = in.nextInt();
int h = in.nextInt();
int w = in.nextInt();
arr.add(new Brick(s, h, w));
}
System.out.println(getMaxHeight(arr));
}
public static int getMaxHeight(ArrayList<Brick> arr) {
int answer = 0;
Collections.sort(arr);
dy[0] = arr.get(0).h;
answer = dy[0];
for (int i = 1; i < arr.size(); i++) { //dy
int max_h = 0;
for (int j = i - 1; j >= 0; j--) {
if (arr.get(j).w > arr.get(i).w && dy[j] > max_h) {
max_h = dy[j];
}
}
dy[i] = max_h + arr.get(i).h;
answer = Math.max(answer, dy[i]);
}
return answer;
}
public static class Brick implements Comparable<Brick> {
public int s, h, w;
Brick(int s, int h, int w) {
this.s = s;
this.h = h;
this.w = w;
}
@Override
public int compareTo(Brick o) {
return o.s - this.s;
}
}
}
5. 동전교환
package com.codingtest.Algorithm.Chapter3.DP;
import java.util.Arrays;
import java.util.Scanner;
public class 동전교환 {
static int num, change;
static int[] dy;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
num = in.nextInt();
int[] arr = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = in.nextInt();
}
change = in.nextInt();
dy = new int[change + 1];
System.out.println(minCoinNum(arr));
}
public static int minCoinNum(int[] coins) {
Arrays.fill(dy, Integer.MAX_VALUE);
dy[0] = 0;
for (int i = 0; i < num; i++) {
int coin = coins[i];
for (int j = coin; j <= change; j++) {
dy[j] = Math.min(dy[j - coin] + 1, dy[j]);
}
}
return dy[change];
}
}
6. 최대점수 구하기
package com.codingtest.Algorithm.Chapter10.DP;
import java.util.ArrayList;
import java.util.Scanner;
public class 최대점수_구하기 {
static int num, totalTime;
static int[] dy;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
num = in.nextInt();
totalTime = in.nextInt();
dy = new int[totalTime + 1];
// dy[0] => 0문제 풀었을 때 최대 점수
ArrayList<Question> arr = new ArrayList<>();
for (int i = 0; i < num; i++) {
int score = in.nextInt();
int time = in.nextInt();
arr.add(new Question(score, time));
}
System.out.println(getMaxScore(arr));
}
public static int getMaxScore(ArrayList<Question> questions) {
for (int i = 0; i < num; i++) {
int maxScore = 0;
int s = questions.get(i).score;
int t = questions.get(i).time;
for (int j = totalTime; j >= t; j--) {
dy[j] = Math.max(dy[j], dy[j - t] + s);
}
}
return dy[totalTime];
}
public static class Question implements Comparable<Question> {
public int score, time;
Question(int score, int time) {
this.score = score;
this.time = time;
}
@Override
public int compareTo(Question o) {
return o.score - this.score;
}
}
}
Last updated