분류 전체보기
-
[백준]12896: 스크루지 민호 - JAVA문제풀이/백준 2021. 8. 23. 15:35
[백준]12896: 스크루지 민호 12896번: 스크루지 민호 구두쇠로 유명한 스크루지 민호가 다스리는 천나라가 있다. 천나라에는 N 개의 도시들이 있는데 각각의 도시들 사이에는 양방향 도로로 이어져 있다. 민호는 도시를 세울 때 최소한의 비용만을 www.acmicpc.net 풀이 🪑 탐색과 관련된 문제로 DFS를 사용하여 풀었다. 문제를 잘 이해하는게 중요한 문제 였던 것 같다. 📝 문제의 조건을 살펴보자! N개의 도시를 N-1개의 도로로 연결하며 도로 사이에는 단 한개의 경로만이 존재한다. (트리이다!) 최적의 위치는 소방서에서 다른 도시로 가는 이동 거리 중에 최대가 최소가 되는 지점이다. 도시 간의 거리는 모두 1이다. 도로는 양방향으로 연결되어 있다. 최적의 위치에서 다른 도시에 도착할 때 이동..
-
[백준]22238: 🔫가희와 btd5 - JAVA문제풀이/백준 2021. 8. 20. 15:07
[백준]22238: 가희와 btd5 22238번: 가희와 btd5 첫 번째 공격은 개틀링 거너가 좌표 (0,0)에서 (1,1)방향에 있는 풍선들의 체력을 3 감소 시키는 공격을 하는 것입니다. [그림1] 개틀링 거너의 첫 공격 첫 공격 후, (1, 1)에 있었던 체력이 3이였던 www.acmicpc.net 풀이 🪑 근 3일동안 풀었던 문제이다. 출력초과와 틀렸습니다와 시간초과와 싸웠다. 알고리즘 유형이라고 한다면, 구현 + 이분탐색 이라고 생각한다. 문제에 있는 함정을 유의하자! 📝 문제를 정리해 보자! Drating Gun Tower는 0,0에 하나 있다. Darting Gun Tower가 공격을 하면 공격 방향에 놓인 모든 풍선들은 동일한 damage의 피해를 입는다. Darting Gun Tower..
-
[백준] 22236: 🛫🛬가희와 비행기 - JAVA문제풀이/백준 2021. 8. 18. 16:10
[백준] 22236: 가희와 비행기 22236번: 가희와 비행기 가희는 김포 공항에서 김해 공항까지 비행기를 타고 가려고 합니다. 비행기가 수평 방향으로 1만큼 이동하였을 때, 비행기의 고도는 1만큼 변화합니다. (상승 또는 하강) 비행기가 상승하거나 www.acmicpc.net 풀이 🪑 DP유형 스러운 DP문제로 어렵지 않은 점화식으로 풀 수 있는 문제였다! 📝 문제를 정리해 보자! 수평 방향으로의 이동 변화량과 고도 변화량은 동일하다. 비행기는 착륙까지 비행 방향을 바꾸지 않는다. 즉, 고도만 바뀐다. 수평 방향으로 D만큼 이동했을 때 착륙 지점의 고도는 항상 0이다. 또한 착륙 이전에는 고도가 0이면 안된다. 위의 조건을 모두 만족하여 착륙지점에 착륙하는 경우의 수를 모두 구한다. 🙋♀️ 일단 점..
-
[백준]22234: 💰가희와 은행 - JAVA문제풀이/백준 2021. 8. 16. 17:24
[백준]22234: 💰가희와 은행 22234번: 가희와 은행 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 www.acmicpc.net 풀이 🪑 Queue, PriorityQueue를 활용하는 자료구조 문제이다. 이와 같은 유형은 자주 접해본 유형이었다! 📝 문제가 길어서 어려워 보이지만, 그렇지 않다. 차근차근 정리해 보자! 은행은 창구가 하나이다. 즉, 한 번에 손님 한명만 처리할 수 있다. W - 1초가 지날때 까지 창구에 있는 직원이 처리하는 고객을 출력하면 된다. 손님은 id, 소요 시간, 들어온 시간에 대한 정보를 가지고 있다. 라운드 로빈 방식..
-
[백준]1944: 복제 로봇 - JAVA문제풀이/백준 2021. 8. 14. 19:26
[백준]1944: 복제 로봇 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 풀이 🪑 이 문제는 어떻게 풀어야 하는지 도저히 모르겠었던 문제였다! 로봇이 움직이는 횟수의 합을 최소로 하기 위해서 BFS를 떠올렸지만, K를 만날 때마다 복제가 된다는 조건 때문에 방문 체크를 어떻게 처리해야 할지 걱정되었던 문제였다. 그래서 문제의 '알고리즘 분류'에서 MST라는 힌트를 얻었다. 막상 MST라는걸 알고 나니 되게 쉽게 느껴졌던 문제였다. 📝 문제를 정리해 보자! 모든 열쇠를 찾으면서..
-
[백준]1194: 달이 차오른다, 가자 - JAVA문제풀이/백준 2021. 8. 13. 15:08
[백준]1194: 달이 차오른다, 가자 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 🪑 BFS + 비트마스킹이 결합된 문제이다! 재밌었던 문제였다. 특히 열쇠를 가지고 있는지 여부를 하나씩 계산해 주다가 비트마스킹으로 간편하게 확인할 수 있는 방법을 알게 되고 너무 신세계였다. 📝 문제의 조건을 정리해 보자! 주어진 미로를 탈출하는데 걸리는 최소 이동 횟수를 구한다. 0에서 출발하여 1로 탈출한다 문은 대응하는 열쇠를 먼저 얻어야 열 수 있다. 같은 타입의 열쇠가 여러개..
-
[백준]13418: 학교 탐방하기 - JAVA문제풀이/백준 2021. 8. 12. 17:47
[백준]13418: 학교 탐방하기 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄 www.acmicpc.net 풀이 🪑 MST를 활용한 문제였다. 최소 간선 트리를 구하는 MST를 활용하여 최대 간선 트리도 구해주면 된다. 📝 문제를 정리해 보자! 출발 건물은 0이며 항상 출발 건물에서 모든 건물로 갈 수 있다. 오르막길을 K번 오르면 피로도는 K^2이다. 최악의 피로도, 최소의 피로도를 가지는 경로의 피로도 차이를 구한다. 🔧 문제를 풀어 보자! 간선의 정보를 입력 받을 때 양 방향으로 정보를 입력 받는다. ..
-
[백준]8972: 미친 아두이노 - JAVA문제풀이/백준 2021. 8. 11. 15:48
[백준]8972: 미친 아두이노 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 풀이 🪑 구현 + 탐색 문제였다! 구현 문제 특징은 문제는 어렵지 않으나 구현하는 과정에서 놓칠 수 있는 조건들이 발생하기 쉽고, 문제의 조건에 맞게 구현하되 시간초과가 발생하지 않도록 구현해 주어야 한다. 구현 문제를 풀 때에는 조건을 꼼꼼히! 확인해 주어야 나중에 고생을 덜한다. 📝 문제의 조건을 꼼꼼히! 확인해 보자. 종수의 아두이노를 먼저 이동시킨다. 가만히 있는 경우를 포함해 9가지 경우의 이동 범위를 갖는다. 종수의 ..