- 생각
카드 N개를 구매하는데 최소 비용을 고르는 문제이다.
그래서 카드 N개를 구하는 비용을 카드가 N개 들어있는 카드팩으로 초기 설정해주면 쉽게 풀 수 있다.문제를 해석해보면
- 카드 N개를 구매해야한다.
- 카드팩에 들어있는 카드가 적은 것부터 산다.
- 카드 N개를 구매하는데 드는 비용의 최소를 구하는 문제이다.
DP를 풀때 일반항 형태로 정의하는 것이 중요하다.
일단, 케이스 단위로 생각해보자.
카드 i개를 구매하는 방법은?
- 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구입한다.
- 카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구입한다.
- 카드 3개가 들어있는 카드팩을 구매하고, 카드 i-3개를 구입한다.
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N, dp[], array[];
public static void main(String[] args) throws Exception {
SetData();
dp();
System.out.println(dp[N]);
}
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
array = new int[N + 1];
dp = new int[N + 1];
for (int i = 1; i <= N; i++)
array[i] = in.nextInt();
}
private static void dp() {
for(int i = 1; i <= N; i++){
dp[i] = array[i];
for(int j = 1; j <= i; j++){
dp[i] = Math.min(dp[i], dp[i-j]+array[j]);
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
'algorithm' 카테고리의 다른 글
[BOJ/JAVA] 백준 2096번 : 내려가기 (0) | 2021.02.16 |
---|---|
[BOJ/JAVA] 백준 1987번 : 알파벳 (0) | 2021.02.10 |
[BOJ/JAVA] 백준 2146번 : 다리 만들기 (0) | 2021.02.09 |
[BOJ/JAVA] 백준 14500번 : 테트로미노 (0) | 2021.02.08 |
[BOJ/JAVA] 백준 15684번 : 사다리 조각 (0) | 2021.02.08 |