<stdio.han>

[문제 링크]

https://www.acmicpc.net/problem/2156

[난이도]

- Silver 1

[알고리즘]

- DP

[코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] wine = new int[n+1];
        for (int i = 1; i <= n; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }

        if (n == 1) {
            System.out.println(wine[1]);
            return;
        }

        // 초기값 설정
        int[] dp = new int[n+1];
        dp[1] = wine[1];
        if (n > 1) {
            dp[2] = wine[1] + wine[2];
        }

        // 점화식 도출
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]));
        }
        /**
         * dp[i-1]  = i번째 잔을 안마시는경우
         * dp[i-2] + wine[i] = i-1번째잔을 마시지 않고 현재와인을 마시는 경우
         * dp[i-3] + wine[i-1] + wine[i] = i번째 잔과 i-1번째 잔을 마시고, i-2번째 잔을 마시지 않는 경우
         */

        System.out.println(dp[n]);
    }
}

[풀이]

1. DP 배열 정의: dp[i]는 i번째 포도주 잔까지 최대로 마실 수 있는 포도주의 양을 의미합니다.
2. 점화식 수립:
   • dp[i]는 세 가지 경우 중 최댓값이 됩니다:
     1. i번째 잔을 마시지 않는 경우: dp[i-1]
     2. i번째 잔을 마시고, i-1번째 잔을 마시지 않는 경우: dp[i-2] + wine[i]
     3. i번째 잔과 i-1번째 잔을 마시고, i-2번째 잔을 마시지 않는 경우: dp[i-3] + wine[i-1] + wine[i]
3. 초기 조건 설정:
   • dp[0]은 첫 번째 잔을 마시는 경우입니다.
   • dp[1]은 첫 번째와 두 번째 잔을 마시는 경우입니다.
   • dp[2]은 세 번째 잔까지의 최댓값을 고려합니다.

[문제 링크]

https://www.acmicpc.net/problem/2529

[난이도]

- Silver 1

[알고리즘]

- 백트래킹

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int k;
    static char[] operators;
    static boolean[] visited = new boolean[10];
    static List<String> results = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());

        // 공백을 없애고 각 글자를 char array로 담는다
        operators = br.readLine().replace(" ", "").toCharArray();

        solve("", 0);

        results.sort(String::compareTo); // results 리스트를 사전순으로 정렬

        System.out.println(results.get(results.size() - 1)); // 최댓값
        System.out.println(results.get(0)); // 최솟값
    }

    /**
     *
     * @param num 현재까지 생성된 숫자
     * @param index 현재 처리중인 숫자자리
     */
    static void solve(String num, int index) {
        if (index == k + 1) {
            results.add(num);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (visited[i]) continue; // 이미사용한 숫자라면 통과

            // index가 0일경우에는 비교할 숫자가 하나밖에 없기때문에 다음숫자로 넘어감
            // 혹은 비교한 두 숫자가 주어진 부등호의 조건과 맞다면 계속 진행
            if (index == 0 || check(num.charAt(index - 1) - '0', i, operators[index - 1])) {
                visited[i] = true;
                solve(num + i, index + 1);
                visited[i] = false; // 완전탐색을 위해 복구
            }
        }
    }

    static boolean check(int a, int b, char operator) {
        if (operator == '<') return a < b;
        else return a > b;
    }
}

[풀이]

백트래킹 알고리즘을 활용할 때 넘겨주는 매개변수를 num : 현재까지 생성된 숫자, index 현재 처리중인 숫자 를 넘겨준다.

for문을 돌며 숫자 두개를 입력받은 부등호와 비교해 참일경우에만 다음숫자를 진행한다.

[문제 링크]

https://www.acmicpc.net/problem/2023

[난이도]

- Gold 5

[알고리즘]

- 백트래킹

[코드]

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));
        int N = Integer.parseInt(br.readLine());

        // 초기 신기한 소수 시작 자리 설정
        int[] primeStarts = {2, 3, 5, 7};

        // 결과를 저장할 리스트
        List<Integer> results = new ArrayList<>();

        // 신기한 소수 찾기
        for (int start : primeStarts) { // 일의 자리가 2, 3, 5, 7 이여야함
            findAmazingPrimes(N, start, 1, results);
        }

        // 결과 정렬 및 출력
        Collections.sort(results); // 오름차순으로 정렬 후 출력
        for (int num : results) {
            System.out.println(num);
        }
    }

    // 재귀적으로 신기한 소수를 찾는 함수

    /**
     *
     * @param N N자리
     * @param current 현재 숫자
     * @param length 현재 숫자의 길이
     * @param results 현재 숫자의 길이가 N자리가 되면 results 리스트에 추가함
     */
    private static void findAmazingPrimes(int N, int current, int length, List<Integer> results) {
        if (length == N) { // N자리가 될 때까지 반복
            results.add(current);
            return;
        }

        // 다음 자리수로 확장
        for (int i = 1; i <= 9; i++) {
            int next = current * 10 + i;
            if (isPrime(next)) { // 소수면 true
                findAmazingPrimes(N, next, length + 1, results);
            }
        }
    }

    // 소수 판별 함수
    private static boolean isPrime(int num) {
        if (num < 2) return false; // 2보다 작으면 소수가 아님
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false; // num이 i로 나눠떨어지면 소수가 아님
        }
        return true;
    }
}

[풀이]

일의 자리가 소수인것은  2, 3, 5, 7 밖에 없으므로 2, 3, 5, 7을 기준으로 신기한 소수를 찾는다. 소수 판별함수는 숫자가 어떤 특정한 수로 나눠떨어지면 소수가 아닌 성질을 활용한다.

[문제 링크]

https://www.acmicpc.net/problem/13023

[난이도]

- Gold 5

[알고리즘]

- 백트래킹

[코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static ArrayList<ArrayList<Integer>> adj;
    static boolean[] visited;
    static boolean found = false;

    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());

        adj = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>()); // 정점의 수만큼 생성
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj.get(a).add(b); // 양방향 간선
            adj.get(b).add(a); // 양방향 간선
        }

        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            if (!found) { // ABCDE가 존재하면 true 발견하지 못했다면 false
                dfs(i, 0);
            }
        }

        System.out.println(found ? 1 : 0);
    }

    static void dfs(int node, int depth) {
        if (depth == 4) { // depth가 4면 ABCDE가 서로 연결되어있다는 뜻
            found = true;
            return;
        }

        visited[node] = true;

        for (int next : adj.get(node)) {
            if (!visited[next]) { // 중복방문을 방지
                dfs(next, depth + 1);
                if (found) return;
            }
        }

        visited[node] = false; // 완전탐색을위해 다시 false로 변경
    }
}

[풀이]

이중 ArrayList로 인정리스트인 Adjacency list를 선언해준후.

각 정점을 기준으로 dfs를 반복해 depth가 4인경우를 찾아준다.

depth가 4일경우 ABCDE가 친구인 경우이다.

찾았다면 1을 못찾았다면 0을 출력한다.

[문제 링크]

https://www.acmicpc.net/problem/2573

[난이도]

- Gold 4

[알고리즘]

- BFS

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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());

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int year = 0;
        while (true) {
            year++;
            // 1년 경과 후 빙산의 높이를 줄입니다.
            int[][] nextMap = new int[N][M];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > 0) {
                        int count = 0;
                        for (int d = 0; d < 4; d++) {
                            int ni = i + dx[d];
                            int nj = j + dy[d];
                            if (map[ni][nj] == 0) {
                                count++;
                            }
                        }
                        nextMap[i][j] = Math.max(0, map[i][j] - count);
                    }
                }
            }
            map = nextMap;

            // 빙산 덩어리 개수를 셉니다.
            int count = countIcebergs();
            if (count == 0) {
                // 모든 빙산이 녹음
                System.out.println(0);
                break;
            } else if (count > 1) {
                // 두 개 이상의 덩어리로 분리됨
                System.out.println(year);
                break;
            }
        }
    }

    static int countIcebergs() {
        visited = new boolean[N][M];
        int count = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] > 0 && !visited[i][j]) {
                    bfs(i, j);
                    count++;
                }
            }
        }

        return count;
    }

    static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

            for (int d = 0; d < 4; d++) {
                int nx = cx + dx[d];
                int ny = cy + dy[d];

                if (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] > 0 && !visited[nx][ny]) {
                    queue.add(new int[] {nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}

[풀이]

문제를 하나하나 풀어 여러 단계로 나누어보면 간단한문제이다. 

1. 1년이 지난후의 지도를 새로 작성한다.

2. 새로운 지도의 빙산개수를 센다.

3. 빙산개수가 0개 혹은 2개이상일 경우 종료한다.

4. 빙산개수가 1개일 경우 1~2를 반복한다.

[문제 링크]

https://www.acmicpc.net/problem/13549

[난이도]

-Gold 5

[알고리즘]

- BFS

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int max = 100000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        boolean[] visited = new boolean[max + 1];

        // BFS를 위한 큐 초기화
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{N, 0});

        int answer = Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int current = tmp[0]; // 현재 위치
            int time = tmp[1];
            visited[current] = true;

            // 동생의 위치에 도달하면 종료
            if (current == K) {
                answer = Math.min(answer, time);
            }

            // 가능한 이동
            if (current * 2 <= max && !visited[current * 2]) {
                queue.offer(new int[]{current * 2, time});
            }
            if (current + 1 <= max && !visited[current + 1]) {
                queue.offer(new int[]{current + 1, time + 1});
            }
            if (current - 1 >= 0 && !visited[current - 1]) {
                queue.offer(new int[]{current - 1, time + 1});
            }
        }
        System.out.println(answer);
    }
}

[풀이]

순간이동할때와 걸어서 이동할때 모두를 고려해서 계산해야 한다.

[문제 링크]

https://www.acmicpc.net/problem/2589

[난이도]

- Gold 5

[알고리즘]

- BFS

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int L, W;
    static char[][] graph;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        L = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        graph = new char[L][W];
        Queue<int[]> LandPos = new LinkedList<>();
        for (int i = 0; i < L; i++) {
            String input = br.readLine();
            for (int j = 0; j < W; j++) {
                graph[i][j] = input.charAt(j);
                if (graph[i][j] == 'L') {
                    LandPos.add(new int[]{i, j});
                }
            }
        }

        int Treasure = 0;
        while (!LandPos.isEmpty()) {
            int[] Land = LandPos.poll();
            int LandX = Land[0];
            int LandY = Land[1];
            Treasure = Math.max(Treasure, bfs(LandX, LandY));
        }
        System.out.println(Treasure);
    }

    static int bfs(int LandX, int LandY) {
        int max = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{LandX, LandY, 0});
        boolean[][] visited = new boolean[L][W];
        visited[LandX][LandY] = true;
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            max = Math.max(max, count);
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < L && ny >= 0 && ny < W) {
                    if (!visited[nx][ny]) {
                        if (graph[nx][ny] == 'L') {
                            visited[nx][ny] = true;
                            queue.add(new int[]{nx, ny, count + 1});
                        }
                    }
                }
            }
        }
        return max;
    }
}

[풀이]

입력을 받을 때 모든 육지인 좌표를 큐에 담아둔 후, 큐에서 하나씩 꺼내며 해당 좌표를 시작으로 4방탐색을 반복해서(육지의 개수만큼) 실행해야 한다. 4방탐색을 하며 한칸 이동할 때 마다 count를 1씩 증가시키고 그 count의 최대값 return 해준다. return 해준 값들 중 최대값을 다시 찾아 출력해준다.

[문제 링크]

https://www.acmicpc.net/problem/1389

[난이도]

- Silver 1

[알고리즘]

- BFS

[코드]

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());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());


        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        int KB[] = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            int[] distance = new int[N + 1];
            Arrays.fill(distance, -1);
            distance[i] = 0;
            while (!queue.isEmpty()) {
                int current = queue.poll();
                for (int next : graph.get(current)) {
                    if (distance[next] == -1) {
                        distance[next] = distance[current] + 1;
                        queue.add(next);
                    }
                }
            }
            int sum = 0;
            for (int j = 1; j < N + 1; j++) {
                sum += distance[j];
            }
            KB[i] = sum;
        }

        int min = Integer.MAX_VALUE;
        int answer = 0;
        for (int i = 1; i < N + 1; i++) {
            if (KB[i] < min) {
                min = KB[i];
                answer = i;
            }
        }
        System.out.println(answer);
    }
}

[풀이]

이중 list를 선언해 각 정점과 양방향으로 연결된 정점을 초기화해준다.

정점과 연결된 다른 정점과의 거리를 distance 배열에 추가한다. 이 로직을 N번 반복해 각 정점을 기준으로 계산해준다.

            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            int[] distance = new int[N + 1];
            Arrays.fill(distance, -1);
            distance[i] = 0;
            while (!queue.isEmpty()) {
                int current = queue.poll();
                for (int next : graph.get(current)) {
                    if (distance[next] == -1) {
                        distance[next] = distance[current] + 1;
                        queue.add(next);
                    }
                }
            }

계산한 케빈베이컨 수중 가장 작은값의 인덱스를 출력해준다.

        for (int i = 1; i < N + 1; i++) {
            if (KB[i] < min) {
                min = KB[i];
                answer = i;
            }
        }