난로
문제 설명
N명의 친구들이 방에 놀러오고, 구사과는 친구가 올 때마다 방에 난로를 켜야한다.
난로를 키는 횟수는 고정되어 있고, 구사과는 난로를 켜놓는 시간을 최소화 하고싶다.
최소 난로를 키는 시간은 얼마인가?해결
동시에 방문하는 경우는 없으므로
친구들이 1시, 5시, 10시, 14시에 들어았으면 위 그림과 같이 진행한다.
우선 첫번째 친구가 올 때 성냥은 무조건 써야한다. 하지만 그 이후에는
내가 난로를 계속 켜놓던가 아니면 다시 꺼서 다음 친구가 올 때 키는
2가지 경우가 있는데, 텀이 가장 작은 부분을 선택하는게 최적이다.코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
long[] a= new long[n];
List<Long> v = new ArrayList<>();
for(int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
long sum = a[n - 1] - a[0] + 1L;
for(int i = 1; i < n; i++) {
v.add(a[i] - a[i - 1] - 1L);
}
Collections.sort(v);
k -= 1;
for(int i = v.size() - 1; i >= 0; i--) {
if(k == 0) {
break;
}
sum -= v.get(i);
k -= 1;
}
System.out.println(sum);
}
}2xN 예쁜 타일링
문제 설명
2 x 1, 2 x 2 타일 2개를 사용해 바닥을 타일링 해야한다. 각 타일은 이쁨 정도가 있고,
그 중에서 가장 큰 이쁨을 만드는게 문제이다.해결
그리디적으로 접근할려다가 잘 안돼서 그냥 DP로 풀었다.
dp[y][x] = 현재 2 x y 까지 와 있는 상태고, 지금까지 쓴 2 x 2 타일의 개수가 x일 때
가장 큰 이쁨의 수
dp[y][x] = max(2 * 2를 쓸 수 있으면 쓴다, 2 * 1을 쓴다)코드
import java.util.*;
public class Main {
static int N, A, B;
static long[][] dp = new long[2001][2001];
static long[] a;
static long[] b;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
A = sc.nextInt();
B = sc.nextInt();
a = new long[A];
b = new long[B];
for(int i = 0; i < A; i++) {
a[i] = sc.nextLong();
}
for(int i = 0; i < B; i++) {
b[i] = sc.nextLong();
}
for(int i = 0; i < 2000; i++) {
for(int j = 0; j < 2000; j++) {
dp[i][j] = -1;
}
}
Arrays.sort(a);
Arrays.sort(b);
System.out.println(go(0, 0));
sc.close();
}
public static long go(int x, int y) {
if(x == N) {
return 0;
}
if(dp[x][y] != -1)return dp[x][y];
int twoStart = B - y - 1;
int oneStart = A - (x - y * 2) - 1;
dp[x][y] = (long)(-2000000000);
if(oneStart >= 0) {
long cnt = go(x + 1, y);
if(cnt >= 0) dp[x][y] = cnt + a[oneStart];
}
if(x + 2 <= N && twoStart >= 0) {
long cnt = go(x + 2, y + 1);
if(cnt >= 0) {
dp[x][y] = Math.max(dp[x][y], cnt + b[twoStart]);
}
}
return dp[x][y];
}
}
동전
문제 설명
1, 5, 10, 25원 동전들이 있고, X원을 커피를 살려고하는데 사용하는 동전의 개수를
최대화 하라는 문제해결
1, 5원은 10, 25원을 다 만들 수 있지만, 10원은 25원을 만들 수 없어서 그리디적으로
한번에 처리할 수 없다. X 범위는 10000을 넘어가지 않아서 10원은 최대 1000개, 25원
은 최대 400개를 사용할 수 있으므로, 10원을 x개, 25원을 y개 썼을 때 최대 동전의
개수를 구하도록 할 수 있다.코드
import java.util.*;
public class Main {
private static int X, A, B, C, D;
private static int[] tmpAns = new int[4]; // 임시 답
private static int[] realAns = new int[4]; // 답
public static int go(int x) {
if(x - (A + 5 * B) > 0) {
return -1;
}
tmpAns[1] = Math.min(x / 5, B);
x -= tmpAns[1] * 5;
tmpAns[0] += x;
if(tmpAns[0] > A || tmpAns[1] > B) return -1;
// B를 사용한 개수중에서 1로 바꿀 수 있으면 바꾸는게 좋다.
int cnt = Math.min((A - tmpAns[0]) / 5, tmpAns[1]);
tmpAns[0] += cnt * 5;
tmpAns[1] -= cnt;
if(tmpAns[0] > A || tmpAns[1] > B) return -1;
return tmpAns[0] + tmpAns[1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
X = sc.nextInt();
A = sc.nextInt();
B = sc.nextInt();
C = sc.nextInt();
D = sc.nextInt();
B = Math.min(B, 2000);
C = Math.min(C, 1000);
D = Math.min(D, 400);
for(int i = 0; i < 4; i++) {
tmpAns[i] = 0;
realAns[i] = 0;
}
int ans = 0;
for(int i = 0; i <= C; i++) {
for(int j = 0; j <= D; j++) {
int cnt = i * 10 + j * 25;
if(cnt > X) break;
tmpAns[0] = 0;
tmpAns[1] = 0;
tmpAns[2] = i;
tmpAns[3] = j;
int cnt2 = go(X - cnt);
if(cnt2 == -1) continue;
if(ans < i + j + cnt2) {
ans = i + j + cnt2;
for(int k = 0; k < 4; k++) {
realAns[k] = tmpAns[k];
}
}
}
}
for(int i = 0; i < 4; i++) {
System.out.print(realAns[i] + " ");
}
sc.close();
}
}
Wow