Problem Solving/BOJ

    [백준, BOJ 2022] 사다리 (java)<img src=">
    Problem Solving/BOJ

    [백준, BOJ 2022] 사다리 (java)

    https://www.acmicpc.net/problem/2022메모리: 14,576 KB , 시간: 112 ms사용 알고리즘: 이분 탐색, 수학, 피타고라스 정리수학 공식이 적용되는 것 같은데, 적절한 공식이 떠오르지 않아 블로그를 참고했다. 공식을 대입하여, 이분 탐색으로 두 건물 사이의 거리를 오차 범위 이내에 오도록 하는 값을 찾으면 된다.이분 탐색 시작 시에 값의 범위는 0 ~ Math.min(x, y)인데, 두 건물 사이의 거리가 사다리의 길이보다 길 수는 없기 때문이다.res가 c보다 높은 곳에 위치한다면, 가운데 값을 크게 해야 더 낮은 res를 구할 수 있기 때문에 이분 탐색의 왼쪽 값을 변경해 주고res가 c보다 낮은 곳에 위치한다면, 가운데 값을 낮게 해야 더 높은 res를 구할 수 ..

    [백준, BOJ 1581] 락스타 락동호 (java)
    Problem Solving/BOJ

    [백준, BOJ 1581] 락스타 락동호 (java)

    https://www.acmicpc.net/problem/1581메모리: 14,200 KB , 시간: 124 ms사용 알고리즘: 많은 조건 분기FF가 있다면 무조건 모든 FF를 먼저 넣어주는 것이 좋다.이후 FS가 있다면 FS를 하나 넣어 느리게 시작하는 음악을 넣어주러 가고, 또 모든 SS를 넣어준다.이후 SF와 FS를 번갈아가면서 넣어주면 최대한 많은 곡을 넣어줄 수 있다. 이를 if문을 통해 조건 분기만 잘 구현해주면 된다.import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args..

    [백준, BOJ 17142] 연구소 3 (java)
    Problem Solving/BOJ

    [백준, BOJ 17142] 연구소 3 (java)

    https://www.acmicpc.net/problem/17142메모리: 26,156 KB , 시간: 240 ms사용 알고리즘: 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 백트래킹바이러스가 어디에 존재하는지 ArrayList에 담아 따로 관리해 준다.각 바이러스마다 해당 바이러스만 활성화했을 때, 모든 곳에 바이러스를 확산시키기 위해 얼마만큼 시간이 걸릴지 spread_time 배열에 정보를 저장해 둔다.바이러스들 중 M개의 바이러스를 백트래킹을 통해 골라준 후, 고른 M개의 바이러스들을 활성화시켰을 때 최대 시간을 구해준다.M개의 바이러스 조합 중 최대 시간이 가장 짧은 시간을 답으로 출력한다. 이 문제를 해결하면서 한 가지 헷갈렸던 조건은 활성 바이러스가 비활성 바이러스가 ..

    [백준, BOJ 18116] 로봇 조립 (java)
    Problem Solving/BOJ

    [백준, BOJ 18116] 로봇 조립 (java)

    https://www.acmicpc.net/problem/18116메모리: 306,680 KB , 시간: 1,232 ms사용 알고리즘: 유니온 파인드같은 로봇의 부품인지 알기 위해 유니온 파인드를 사용하였다.만약 두 부품이 같은 로봇의 부품인지 알게 되었다면, 각자 알고 있던 부품의 개수를 더해준다.import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int[] parent; static int[] count; public static void main(String[] args) t..

    [백준, BOJ 1799] 비숍 (java)
    Problem Solving/BOJ

    [백준, BOJ 1799] 비숍 (java)

    https://www.acmicpc.net/problem/1799메모리: 15,996 KB , 시간: 192 ms사용 알고리즘: 백트래킹일단 이 문제에서 내가 생각해 낸 아이디어는,체스판에서 왼쪽 위 -> 오른쪽 아래로 내려오는 라인들을 그었을 때, 각 라인 위에 위치한 비숍들은 다른 라인에 영향을 줄 수 없다.마찬가지로 오른쪽 위부터 왼쪽 아래로 내려오는 라인들을 그었을 때, 각 라인 위에 위치한 비숍들은 다른 라인에 영향을 줄 수 없다. 이 아이디어를 가지고 오른쪽 위 -> 왼쪽 아래로 내려오는 라인들을 해당 라인에서 비숍을 하나 고르고 다른 라인에서 비숍을 고르러 가는 방법으로 백트래킹 했다.(비숍을 하나 골랐을 때, 왼쪽 위 -> 오른쪽 아래 라인에 이미 비숍이 있으면 놓을 수 없다.)그런데 이 ..

    [백준, BOJ 6443] 애너그램 (java)
    Problem Solving/BOJ

    [백준, BOJ 6443] 애너그램 (java)

    https://www.acmicpc.net/problem/6443메모리: 34,256 KB , 시간: 496 ms사용 알고리즘: 백트래킹, 문자열입력받은 문자열에서 사용한 문자의 개수를 담는 visited 배열을 만들어,인덱스에 해당하는 문자가 몇 개 사용됐는지 체크해준다. combi 메소드에서 백트래킹을 통해 현재 사용할 수 있는 문자 중 사전 순으로 빠른 문자부터 스택에 담아주고,사용할 수 있는 문자 개수를 줄여주며 애너그램 조합을 구해주는 방식을 사용했다.import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Stack;public class Main { static char[] string; stat..

    [백준, BOJ 2211] 네트워크 복구 (java)
    Problem Solving/BOJ

    [백준, BOJ 2211] 네트워크 복구 (java)

    https://www.acmicpc.net/problem/2211메모리: 131,376 KB , 시간: 864 ms사용 알고리즘: 데이크스트라, 그래프 이론, 최단 경로이 문제에서 주의해야 할 점은 '슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.'는 점이다.이 부분을 간과하고 호기롭게 크루스칼 알고리즘으로 풀었다가 틀리고 나서야 문제를 다시 보고 이 점을 알았다. 따라서 이 문제는 크루스칼 알고리즘이 아니라 다익스트라 알고리즘을 사용해야 하는데, 관건은 최단 거리에 사용한 회선 정보를 출력해야 하는 것이다.이 문제를 해결하기 위해 다익스트라에서 사용하는 우선순위 큐에 넣을 Route 클래스를 만들고 객체에 경로의 마지막..

    [백준, BOJ 1520] 내리막 길 (java)
    Problem Solving/BOJ

    [백준, BOJ 1520] 내리막 길 (java)

    https://www.acmicpc.net/problem/1520메모리: 34,424 KB , 시간: 396 ms사용 알고리즘: 깊이 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int M, N; static int[][] map; static int[][] can_move; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; public static void main(Stri..

    [백준, BOJ 16432] 떡장수와 호랑이 (java)
    Problem Solving/BOJ

    [백준, BOJ 16432] 떡장수와 호랑이 (java)

    https://www.acmicpc.net/problem/16432메모리: 16,364 KB , 시간: 176 ms사용 알고리즘: 깊이 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int N; static boolean[][] rice_cake; static boolean[][] visited; static int[] pick; public static void main(String[] args) throws Exception{ Buf..

    [백준, BOJ 1092] 배 (java)
    Problem Solving/BOJ

    [백준, BOJ 1092] 배 (java)

    https://www.acmicpc.net/problem/1092메모리: 16,204 KB , 시간: 156 ms사용 알고리즘: 그리디 알고리즘, 정렬import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Collections;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

티스토리툴바