분류 전체보기
-
[백준]22252:🕵️♂️ 정보 상인 호석 - JAVA문제풀이/백준 2021. 7. 27. 15:45
[백준]22252: 정보 상인 호석 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 풀이 🪑 우선순위큐, 해쉬맵을 활용한 자료구조 문제이다. 📝 문제의 조건들을 정리해 보자. 가치 순으로 가장 비싼 정보들을 구매한다. 한번 거래한 정보는 파기된다. 1로 시작하는 쿼리는 정보를 얻은 고릴라와 가지고 있는 정보 가치를 의미한다. 2로 시작하는 쿼리는 거래할 고릴라와 구매하려는 정보의 개수를 의미한다. 정보는 시간 순서대로 주어진다. 🤔 처음에는 문제가 잘 이해가 되질 않아 예제를 보며 따라가 보았다. 예제를 ..
-
[백준]22251: 🤷♂️빌런 호석 - JAVA문제풀이/백준 2021. 7. 26. 13:56
[백준]22251: 빌런 호석 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 풀이 🪑 굉장히 재미있는 구현 문제였다. 📝 문제의 조건을 정리해 보자. 7개의 표시등으로 이루어진 디스플레이를 K개의 자리수로 표현한다. 디스플레이 표시등 중에 최소 1개, 최대 P개를 반전시킨다. (자기자신으로 반전하는 경우는 제외한다.) 반전 이후에도 올바른 수가 보여져야 하며 수는 1이상 N이하여야 한다. 반전시킬 표시등을 고를 수 있는 경우의 수를 계산한다. 🙋♀️ 문제 풀이 과정을 도출해 내는 과정을 다음과 같았다. - 처음에는 '백트랙킹'으로 반전시킬 표시등의 수를 골라 반전시켜서 수를 만들 수 있는지, ..
-
[백준]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문제였다. 문제의 조건을 정리해 보자. 전리품은 한 번이라도 피해를 준 플레이어에게 지급된다. 최대 몇명의 플레이어가 전리품을 가져갈 수 있는지 알아낸다. 각각의 플레이어는 보스에게 최단거리로 이동하여 보스 칸에 도달하자마자 공격을 시작한다. 플레이어의 공격은 동시에 이뤄지며 같은 위치에 여러 플레이어가 위치..