문제풀이/백준
-
[백준]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가지 경우의 이동 범위를 갖는다. 종수의 ..
-
[백준]18119: 단어 암기 - JAVA문제풀이/백준 2021. 8. 10. 15:07
[백준]18119: 단어 암기 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 풀이 🪑 문제는 굉장히 간단하다. 각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하는 문자열 문제이다! 📝 문제를 정리해 보쟈. 단어는 소문자로만 되어 있으며 단어 안에 모든 알파벳을 알면 그 단어를 안다고 한다. 각 쿼리 마다 완전히 알고 있는 단어의 개수를 출력한다. 모음은 완벽하게 외웠다. 잊어버릴 일이 없다. 🙋♀️ 처음에는 시간복잡도를 생각해 보았다. O(NM)으로 문자를 하나씩 확인하며 완탐으로 문제를 푼다고 했을때..
-
[백준]20437: 문자열 게임 2 - JAVA문제풀이/백준 2021. 8. 9. 14:03
[백준]20437: 문자열 게임 2 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 풀이 🪑 처음 보자마자 굉장히 쉬운 문제라고 생각 했었엇었섯다. 투포인터를 사용하여 구현했었다. 그런데 시간초과가 발생했고,, 아무리 생각해도 다른 방법이 떠오르질 않아 다른 분의 풀이를 참고하였다. 🙋♀️ 풀이를 보고 나니,,흠,, 뭔가 시간복잡도는 투포인터를 사용하는 방식과 큰 차이가 없어 보여서 더 의아해지긴 했다. 그래도 알파벳 별로 개수를 입력받는다 라는 큰 힌트를 얻어 다시 풀어 보았다! 📝 문제의 조건을 정리해..
-
[백준]17472: 다리 만들기 2 - JAVA문제풀이/백준 2021. 8. 6. 15:11
[백준]17472: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 🪑 구현 + BFS + DFS + MST + 완탐의 아이디어가 들어간 문제였다. 이 중에서 가장 중요한 부분은 MST이다. 📝 문제의 조건을 정리해 보자. 다리의 방향이 중간에 바뀔 수 없으며 길이는 2 이상이어야 한다. 섬을 모두 연결하는 다리의 최소 길이를 구한다. 다리는 교차될 수 있으며 교차되는 경우 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 모든 섬을 연결하는 것이 불가능 하면 -1을 ..