| 문제번호 | 제목 | 난이도 |
|---|---|---|
| 8980번 | 택배 | 골드 1 |
| 10775번 | 공항 | 골드 2 |
| 2293번 | 동전 1 | 골드 5 |
| 16236번 | 아기 상어 | 골드 3 |
8980번 택배
해결 코드:
import java.io.*;
import java.util.*;
class Lists{
int start;
int end;
int count;
public Lists(int start, int end, int count){
this.start = start;
this.end = end;
this.count = count;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(br.readLine());
Lists[] list = new Lists[m];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int count = Integer.parseInt(st.nextToken());
list[i] = new Lists(start, end, count);
}
Arrays.sort(list, (o1, o2) -> {
if(o1.end == o2.end){
return o1.start - o2.start;
}
return o1.end - o2.end;
});
int[] arr = new int[n+1];
for (int i = 1; i < n; i++) {
arr[i] = c;
}
int ans = 0;
for (int i = 0; i < m; i++) {
Lists li = list[i];
int max = Integer.MAX_VALUE;
for (int j = li.start; j < li.end; j++) {
max = Math.min(max, arr[j]);
}
if(max >= li.count){
for (int j = li.start; j < li.end; j++) {
arr[j] -= li.count;
}
ans += li.count;
}else{
for (int j = li.start; j < li.end; j++) {
arr[j] -= max;
}
ans += max;
}
}
bw.write(ans +"");
br.close();
bw.close();
}
}
해결 키포인트:
- 배송 정보 리스트 정렬을 다음과 같이 해야한다:
-> 1번 우선순위: 받는 마을, 2번 우선순위: 보내는 마을 - 각 마을 별로, 최대로 보낼 수 있는 박스의 개수를 설정해둔다.
-> 초기 용량은 트럭의 용량 c로 지정한다 - 배송 정보 리스트를 확인하면서 보내는 구간부터 받는 구간까지 구간 별로
최대로 보낼 수 있는 용량을 계산해서 각 마을별로 보낼 수 있는 박스의 개수를 갱신한다.
고민/풀이흐름:
- 일단 문제를 읽으면서 상태 정보들을 잘 관리해야겠다는 생각을 하게되었다
- 배송정보는 클래스로 만들어서 클래스타입의 리스트로 관리하고, 각 마을별로 배열을 만들어 보낼 수 있는 박스의 개수 상태도 관리한다
- 최대 박스 개수를 보내기 위해 조금 그리디하게 생각해볼 필요가 있다. 따라서 처음에는 보내는 곳, 받는 곳 기준으로 정렬을 진행하였다
- 하지만 반례가 발생하였고, 이번에는 받는 곳 -> 보내는 곳 기준으로 오름차순 정렬을 진행하였다.
- 이후 풀이는 조금 떠올리는데 고민을 많이하였다. 정렬대로만 풀자니 순서 관리가 쉽지가 않고, 다른 방법을 모색하자니 그것도 쉽게 떠오르지 않았다
- 일단 각 마을별로 보낼 수 있는 박스의 개수 상태를 관리하도록 하였다. 이때 초기값은 트럭이 실을 수 있는 최대 용량으로 한다
- 이제 배송 정보를 보면서 각 배송정보의 라인 별로 상태를 관리하면서 값을 갱신해준다.
- 먼저 max에 각 라인에서 보낼 수 있는 최대치를 구해준다.
- 최대치가 만약 현재 배송 정보에서 보내려고 하는 크기보다 크거나 같으면 각 라인에서 그 보내려는 크기를 빼주고 ans에 그 값을 더해준다.
- 최대치가 더 크면 최대치로 배송하는 것이므로 똑같이 라인에서 max를 빼주고 ans에 max를 더해준다
- 해당방식으로 진행하여 ans를 출력하면 정답이 된다.
링크:
10775번 공항
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int g = Integer.parseInt(br.readLine());
int p = Integer.parseInt(br.readLine());
int[] arr = new int[p];
for (int i = 0; i < p; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
parent = new int[g+1];
for (int i = 1; i < g+1; i++) {
parent[i] = i;
}
int ans = 0;
for (int i = 0; i < p; i++) {
int prepare = find(arr[i]);
if(prepare == 0){
break;
}
ans++;
union(prepare, prepare-1);
}
bw.write(ans+"");
br.close();
bw.close();
}
private static int find(int x){
if(x == parent[x]){
return x;
}
return parent[x] = find(parent[x]);
}
private static void union(int x, int y){
x = find(x);
y = find(y);
if(x!= y){
parent[x] = y;
}
}
}
해결 키포인트:
- 문제를 이해하기만 하면 쉽게 풀 수 있다.
- 비행기가 도킹하려고 할 때, 최적의 게이트는 그 비행기가 도킹하고자 하는 게이트이다.
- 만약 해당 게이트에 비행기가 있다면 그 이전 게이트로 도킹하도록 하면 된다.
- 위와 같이 그리디하게 풀면 해결할 수 있으며, 추가로 유니온파인드 까지 이용하면 매우 쉽게 풀 수 있다.
고민/풀이흐름:
- 비행기가 들어오려는 게이트 값들은 배열에 받아둔다
- 유니온 파인드 설정을 마치고, 배열에 있는 값들을 불러와서 그 부모 값을 찾아준다.
- 이때 처음 들어올때는 자기 자신의 게이트에 도킹하게 된다. 만약 자기 자신의 게이트에 이미 도킹이 되어있다면 바로 이전 게이트에 도킹한다. 이때 union을 해준다
- 만약 현재 도킹하려는 게이트가 0이라면 더이상 도킹할 수 없으므로 종료해준다
- 각 순회마다 ans값을 증가시켜서 정답으로 출력해준다.
링크:
2293번 동전 1
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] dp = new int[k+1];
dp[0] = 1;
for (int i = 1; i < n+1; i++) {
int p1 = Integer.parseInt(br.readLine());
for (int j = p1; j < k+1; j++) {
dp[j] += dp[j - p1];
}
}
bw.write(dp[k]+"");
br.close();
bw.close();
}
}
해결 키포인트:
- 너무 어려운 dp...
- 점화식은 힌트 참고했습니다;
- 해당 문제에서 dp 배열은 자릿수를 만들 수 있는 숫자를 의미하도록 정의하였다
- 입력값인 p1으로 각 자릿수를 만들 수 있는 경우를 더하는 방식으로 풀면 된다.
고민/풀이흐름:
- dp[0]은 1로 지정하고 p1부터 k까지 순회하면서 dp[j]에 dp[j-p1]을 더해준다
- p1부터 k까지 1번을 반복한 뒤, dp[k]를 출력한다.
링크:
16236번 아기 상어
해결 코드:
import java.io.*;
import java.util.*;
class Pos{
int y;
int x;
int count;
public Pos(int y, int x, int count) {
this.y = y;
this.x = x;
this.count = count;
}
}
public class Main {
static int count = 0;
static boolean[][] visited;
static int[] dy = {-1,0,0,1};
static int[] dx = {0,-1,1,0};
static int[][] arr;
static int size = 2;
static int eat = 0;
static boolean chk;
static Pos start;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if(arr[i][j] == 9){
start = new Pos(i,j, 0);
arr[i][j] = 0;
}
}
}
while(true){
chk = false;
bfs(n,start);
if(!chk){
break;
}
if(size == eat){
size++;
eat = 0;
}
}
bw.write(count+"");
br.close();
bw.close();
}
private static void bfs(int n, Pos s) {
PriorityQueue<Pos> pq = new PriorityQueue<>((o1, o2) -> {
if(o1.count == o2.count){
if(o1.y == o2.y){
return o1.x - o2.x;
}
return o1.y - o2.y;
}
return o1.count - o2.count;
});
pq.add(s);
visited = new boolean[n][n];
visited[s.y][s.x] = true;
while(!pq.isEmpty()){
Pos now = pq.poll();
if(arr[now.y][now.x] != 0 && arr[now.y][now.x] < size){
arr[now.y][now.x] = 0;
eat++;
count += now.count;
start.count = 0;
start.y = now.y;
start.x = now.x;
chk = true;
return;
}
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if(ny >= 0 && nx >= 0 && ny < n && nx < n && !visited[ny][nx]){
if(arr[ny][nx] <= size){
pq.add(new Pos(ny, nx, now.count+1));
visited[ny][nx] = true;
}
}
}
}
}
}
해결 키포인트:
- BFS와 약간의 구현을 더해주는 방식.
- 하지만 이번 BFS에서는 우선순위 큐를 사용해야 한다.
- 탐색이 종료될 때마다, 시작 위치를 갱신해야하고 주어진 조건에 맞게 상어의 크기보다 작다면 해당 위치를 지워주어야 한다
고민/풀이흐름:
- 문제에서 주어진 조건에 맞춰서 BFS와 구현을 같이 진행하면 되는 문제로 생각하였다
- 먼저 배열에 입력값을 받고 초기값의 위치를 미리 받아둔다.
- 초기값의 위치는 배열로도 받을 수 있지만 문제의 편의를 위해 클래스로 미리 지정해두었다
- 세번째 필드인 count는 지금까지 탐색한 횟수이다
- 먼저 아기상어가 탐색을 더이상 못한다는 플래그를 하나 설정해두었다. chk 불리언을 통해 판단할 것이다
- bfs탐색을 진행한다. 이때 원래의 BFS와 다른점이 일반 큐가 아니라 우선순위 큐를 사용한다는 점이다.
- 왜냐하면 주어진 조건에 맞추기 위해 큐에서 정렬이 지속적으로 이루어져야하기 때문이다
- 가장 가까운 위치, 위쪽, 왼쪽 순으로 상어가 먹이를 먹어야하므로 각각 조건에 맞춰서 오름차순 정렬을 하도록 설정하였다
- 이어서는 기존처럼 bfs 탐색을 진행하면 된다
- 탐색을 할 때는, 상어와 크기가 같더라도 탐색 범위에 넣어준다
- 하지만 현재의 값이 0이 아니고, 상어의 크기보다 작다면 해당 위치를 0으로 초기화, 먹은 숫자 증가, 현재까지 이동한 위치의 수를 더해준다
- 그리고 시작 위치 갱신을 진행하며, chk를 true로 해서 다시 반복하도록 한다
- bfs 종료 후에는 현재 상어의 크기와 먹은 양이 같은지 확인해준다
- 만약 같다면 먹은 양은 0으로 초기화하고 size의 값을 증가시킨다
- 위 과정을 chk가 false가 아닐때까지 반복을 해주고 종료 후에는 count를 출력해주면 정답이 된다.
링크:
Software Developer