알고리즘 재활 12일차 - 백준 2869, 15654, 16236번

 

기다리고 있어요

아우 더워라

 

조금 차올랐다.. 호호

 

달팽이는 올라가고 싶다

 

 

 

간단해도 문제 지문을 잘 읽자.. 꼮!

입력값이 일단 10억이다.. Long 사용해주자

 

먼저 도착하면 B만큼 미끄러지지 않으므로 목표거리는 V-B 가 이동할 거리이다.

이후 시간당 A-B 만큼 이동하므로 이 값으로 목표를 나눴을때 나머지가 있으면 +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));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        Long A = Long.parseLong(st.nextToken());
        Long B = Long.parseLong(st.nextToken());
        Long V = Long.parseLong(st.nextToken());
 
        Long answer = 0L;
 
        if ((V - B) % (A - B) != 0) {
            answer = ((V - B) / (A - B)) + 1;
        } else if ((V - B) % (A - B) == 0) {
            answer = (V - B) / (A - B);
        }
 
        System.out.println(answer);
    }
}

---

 

 

N과 M (5)

 

 

간단한 재귀함수 문제다

중복되지 않게 수열을 출력해주자.

정렬로 작은 수로 나열해주고, depth가 맞으면 StringBuilder에 append 해줬다.

dfs를 활용하면서 visit[]을 통해 중복을 막아주면 꼭 dfs 로직이후 false 처리해주자.

 

import java.io.*;
import java.util.*;
 
public class Main { // N과 M (5)
    public static int N, M;
    public static int [] arr;
    public static StringBuilder sb = new StringBuilder();
    public static boolean[] visit;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(arr);
        visit = new boolean[N];
 
        dfs(0, new int[M]);
 
        System.out.println(sb);
    }
 
    public static void dfs(int depth, int[] output) {
        if (depth == M) {
            for (int num : output) {
                sb.append(num).append(" ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = 0; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                output[depth] = arr[i];
                dfs(depth + 1, output);
                visit[i] = false;
            }
        }
    }
}
 

 

---

아기 상어 

 

 

 

문제를 잘 읽어보면

 

1. N * N 공간은 0, 1~6, 9 의 입력이 주어진다.

2. 상어의 크기는 2로 시작되며 상어는 자신의 몸보다 작은 물고기의 칸으로 이동해 먹을 수 있다.

3. 상어의 몸 크기만큼 물고기를 먹으면 덩치가 1 증가한다.

4. 근처에 먹을 수 있는 물고기가 1마리면 해당 물고기를 잡아먹는다.

5. 근처 물고기가 여러 마리라면 가장 가까운 물고기를 잡아먹는다.

6. 다만 거리가 같은 물고기가 여럿이라면 가장 위쪽 물고기를 잡아먹고, 이마저도 여러마리면 가장 왼쪽을 잡아먹는다.

7. 이동은 1초가 걸리며 행, 열 1칸이 1초이다.

8. 더이상 물고기를 먹을 수 없을때까지의 시간을 출력.

 

지문에 맞춰서 메모장에 psedo code를 짜봤다.

 

• 상어 r, c, 크기, 먹은 물고기 수 객체 생성
• 물고기 위치, 크기, 거리 객체 생성
• 모든 물고기를 먹을때 까지 반복
  • 상어 위치에서 BFS를 활용하여 인근에 상어보다 작은 물고기 탐색 
    • 없다면 반복 종료
  • 거리, 행, 열 순으로 정렬 <우선 순위큐 활용>
  • 정렬된 물고기들에서 poll() 해서 시간 증가 및 물고기 사이즈, 먹은 물고기 수 변경
•  시간 출력

import java.io.*;
import java.util.*;
 
public class Main {
    public static int N;
    public static int[][] map;
    public static Shark babyShark;
    public static int[] dr = {-1, 0, 0, 1}; // 상좌우하 이동
    public static int[] dc = {0, -1, 1, 0};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int tmp = Integer.parseInt(st.nextToken());
                map[i][j] = tmp;
                if (tmp == 9) {
                    babyShark = new Shark(i, j, 2, 0);
                    map[i][j] = 0; // 상어 초기 위치는 빈 칸으로 변경
                }
            }
        }
 
        int time = 0;
        while (true) {
            // 상어 주변 먹을 수 있는 물고기 탐색
            Fish target = findYummyFish();
            if (target == null) break;
 
            int distance = target.distance;
            time += distance;
            babyShark.r = target.r;
            babyShark.c = target.c;
            babyShark.eatCnt++;
            if (babyShark.eatCnt == babyShark.size) {
                babyShark.size++;
                babyShark.eatCnt = 0;
            }
            map[target.r][target.c] = 0; // 물고기를 먹은 자리는 빈 칸으로 변경
        }
 
        System.out.println(time);
    }
 
    public static Fish findYummyFish() {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        queue.add(new int[]{babyShark.r, babyShark.c, 0});
        visited[babyShark.r][babyShark.c] = true;
        
        // 우선순위 큐로 거리 -> 최상단 -> 좌측 
        PriorityQueue<Fish> fishQueue = new PriorityQueue<>((f1, f2) -> {
            if (f1.distance != f2.distance) return f1.distance - f2.distance;
            if (f1.r != f2.r) return f1.r - f2.r;
            return f1.c - f2.c;
        });
 
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1], dist = cur[2];
 
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
 
                if (nr >= 0 && nr < N && nc >= 0 && nc < N && !visited[nr][nc]) {
                    if (map[nr][nc] <= babyShark.size) { // 이동 가능
                        visited[nr][nc] = true;
                        queue.add(new int[]{nr, nc, dist + 1});
                        if (map[nr][nc] > 0 && map[nr][nc] < babyShark.size) {
                            fishQueue.add(new Fish(nr, nc, map[nr][nc], dist + 1));
                        }
                    }
                }
            }
        }
 
        if (fishQueue.isEmpty()) {
            return null;
        }
 
        return fishQueue.poll();
    }
 
    public static class Fish {
        int r, c, size, distance;
 
        public Fish(int r, int c, int size, int distance) {
            this.r = r;
            this.c = c;
            this.size = size;
            this.distance = distance;
        }
    }
 
    public static class Shark {
        int r, c, size, eatCnt;
 
        public Shark(int r, int c, int size, int eatCnt) {
            this.r = r;
            this.c = c;
            this.size = size;
            this.eatCnt = eatCnt;
        }
    }
}