문제풀이/백준
-
[백준]17396: 백도어 - JAVA문제풀이/백준 2021. 7. 25. 22:46
[백준]17396: 백도어 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 풀이 🪑 문제가 좀 복잡해 보여서 그렇지 사실 문제에 필요 없는 정보를 제외하면 그냥 최단거리 문제이당. 📝 문제를 푸는데 필요한 조건만 정리해 보자. 0에서 N-1번째 분기점 까지 가는 최단 거리를 구해준다. 이때 시야 정보도 주어지는데 0이면 해당 분기점일 때 상대 시야에서 보이지 않는다는 의미이고, 1이면 상대 시야에서 보인다는 의미이다. 시야에서 보이지 않으면서 N-1번째 분기점으로 갈 수 있는 최단거리..
-
[백준]2623: 음악프로그램 - JAVA문제풀이/백준 2021. 7. 24. 21:45
[백준]2623: 음악프로그램 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 🪑 우선순위를 위배하지 않는 순서를 결정하는 문제! 위상정렬 문제이다. 📝 문제의 조건을 정리해 보자. 각각의 피디가 가져온 모든 우선순위를 만족하는 순서를 구해야 한다. 불가능할 경우 0을 출력한다. 🔧 구현 과정을 정리해 보자! 정보를 입력받으며 진출간선 정보, 진입 간선의 수를 저장해 준다. 위상 정렬을 하며 우선순위를 위반하지 않는 정렬 순서를 구한다. 가능한 경우 구한 순서를 출력하고, 불가능한 경..
-
[백준]20926: 얼음 미로 - JAVA문제풀이/백준 2021. 7. 23. 17:23
[백준]20926: 얼음 미로 풀이 🪑 구현 + 다익스트라 문제이다. 📝문제의 조건을 정리해보자. 얼음 미로에서는 한 방향으로 이동시 바위나 출구를 만날때 까지 멈출 수 없다. 바깥은 절벽이다. T: 상하좌우로 이동할 수 있다. R: 통과할 수 없으며 부딪히면 멈춘다 H: 이곳에 빠지면 탈출할 수 없다. E: 미로를 탈출하는 유일한 출구이다. 각 위치마다 미끌시간이 존재하며 탈출할 수 있는 최단 미끌시간을 구한다. 🔧 다음과 같은 풀이를 생각해 주었다. 다익스트라를 사용한다. 한번 이동할 때 해당 방향으로 이동할 수 있는지 먼저 확인한다. 이동 가능하면 그 방향으로 갈 수 있는 곳까지 간다. 도착한 후 더 짧은 미끌시간을 계산해 준다. 도착 노드의 최단 미끌시간을 출력한다. 📌 처음엔 70 ~ 80프로 ..
-
[백준]29140: 가운데에서 만나기 - JAVA문제풀이/백준 2021. 7. 23. 15:13
[백준]29140: 가운데에서 만나기 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 풀이 🪑 생각지도 못한 부분에서 헤멨던 문제였다..! 일단 문제를 보자마자 Shortest Path 문제라는 것을 알았고 다익스트라, 플로이드-와샬 알고리즘을 떠올렸다. 📝문제의 조건을 정리해 보자! 도시와 도시를 연결하는 간선은 유향(방향성을 가진다)이다. 왕복 시간은 A -> B -> A이다. 왕복 시간 중 최대가 최소가 되는 도시를 선택한다. 여러개인 경우 오름차순으로 출력한다. 🙋♀️ '최대가 최소'에서 이분탐색 힌트를 얻고 처음에는 이분탐색으로 접근하였다. 도시별로..
-
[백준]22116: 창영이와의 퇴근 - JAVA문제풀이/백준 2021. 7. 21. 14:56
[백준]22116: 창영이와의 퇴근 풀이 🪑 단순 BFS라고 착각할 수 있으나 BFS는 거들 뿐,, 핵심 로직은 이분탐색을 사용해야 하는 문제이다! 📝 문제를 정리해 보자! 1, 1 -> N, N으로 이동한다. (나는 편의를 위해 0, 0 -> N-1, N-1로 생각해 주었다.) 상, 하, 좌, 우로 한 칸씩 이동한다. 인접 격자 사이의 높이차를 경사라고 할 때 지날 수 있는 최대 경사의 최솟값을 구한다. 📌 최대 경사의 최솟값! 이런 문제 유형은 이분탐색 유형이다. 바로 이분탐색으로 풀어야 겠다고 생각했다. 문제 조건에서 경사 높이의 범위를 보면, 1 에서 1000000000사이인걸 알 수 있다. 이 범위의 값을 이분탐색 해 준다. 🔧 문제 구현 과정을 생각해 보자. 격자의 정보를 입력 받는다. 구해야..
-
[백준]20005: 보스몬스터 전리품 - JAVA문제풀이/백준 2021. 7. 20. 15:59
[백준]20005: 보스몬스터 전리품 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 풀이 🪑 입력받는 정보가 많아서 복잡해 보이지만 알고보면 구현 + BFS문제였다. 문제의 조건을 정리해 보자. 전리품은 한 번이라도 피해를 준 플레이어에게 지급된다. 최대 몇명의 플레이어가 전리품을 가져갈 수 있는지 알아낸다. 각각의 플레이어는 보스에게 최단거리로 이동하여 보스 칸에 도달하자마자 공격을 시작한다. 플레이어의 공격은 동시에 이뤄지며 같은 위치에 여러 플레이어가 위치..
-
[백준]14728: 벼락치기 - JAVA문제풀이/백준 2021. 7. 19. 16:04
[백준]14728: 벼락치기 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 풀이 🪑 이러한 문제 유형은 배낭문제(knapsack)이라는 대표적인 DP유형이다. 배낭문제를 예에에전에 풀어본적은 있어서 이 문제가 DP라는건 언뜻 기억이 났지만 접근 방법이 기억 나지 않아 헤멨던 문제이다. DP라는 느낌이 들면 일단 그림을 그려보면서 이해해 보는 것이 가장 좋은 것 같다! 문제의 조건을 살펴보자. 배낭문제와 매핑해서 생각해 보자. 시험의 단원이 의미하는 바는 배낭문제의 ..
-
[백준]2632: 피자판매 - JAVA문제풀이/백준 2021. 7. 17. 16:51
[백준]2632: 피자판매 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 풀이 🪑 손님이 원하는 크기의 피자만큼 판매할 수 있는 경우의 수를 계산하는 문제로 다양한 풀이 방법이 존재하는 문제이다. 먼저 문제의 조건 부터 정리해 보자. A, B의 피자는 다양한 크기의 여러 조각으로 나누어져 있다. 한 종류의 피자를 2조각 이상 판매시 연속된 조각으로 잘라 판매하며 피자 조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자 조각는 A조각으로만 이루어 질 수 있고, B조각으로만 이루어 질..