문제풀이/백준
-
[백준]10800: 컬러볼 - JAVA문제풀이/백준 2021. 9. 14. 18:05
[백준]10800: 컬러볼 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 풀이 🪑 누적합, 투포인터 유형의 문제로 풀이 과정을 생각해 내기가 어려웠지만 재미있는 문제였다. 📝 문제를 정리해 보자! 각각의 플레이어는 자신의 공 색과 다른 색의 공 중에서 크기가 작은 공을 사로잡을 수 있다. 각 플레이어가 사로잡을 수 있는 모든 공들의 크기 합을 출력한다. 공의 색은 1~N의 경우의수가 존재한다. 🔧 문제 푸리 입력 받은 공의 인덱스, 색, 크기 정보를 저장하여 크기 순으로 정렬한다...
-
[백준]16202: MST 게임 - JAVA문제풀이/백준 2021. 9. 8. 14:41
[백준]16202: MST 게임 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 풀이 🪑 문제에서도 알 수 있듯이 MST문제였다. MST라는 것을 알려주지 않았 더라도 전형적인 MST문제이기 때문에 어렵지 않았을 것으로 예상되는 문제였다! 📝 문제를 정리해 보자! N개의 정점과 M개의 양방향 간선으로 이뤄진 그래프가 있다. K턴동안 진행되며 첫 턴에 MST를 구한다. 각 턴이 종료된 후 MST중에서 가중치가 가장 작은 간선을 제거한다. 나머지 간선..
-
[백준]5569: 출근 경로 - JAVA문제풀이/백준 2021. 9. 7. 15:39
[백준]5569: 출근 경로 5569번: 출근 경로 상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대 www.acmicpc.net 풀이 🪑 전형적인 DP유형의 문제라고 볼 수 있다. 그러나 교차로와 관련된 추가 조건이 있었기에 조금 더 생각을 요하는 DP문제였다. 📝 문제를 정리해 보자! 1, 1에서 W,H로 가는 모든 경로의 수를 찾는다. 이때 문제에서는 동쪽, 북쪽으로만 이동 가능하다고 되어 있다. 나는 뒤집어 생각하여 문제를 풀 것이기 때문에 동쪽, 남쪽으로만 이동이 가능하다고 생각하고 풀었다. 교차로를 돈 차량은 그 다음 교차로에서 다시 방향을..
-
[백준]18500: 미네랄 2 - JAVA문제풀이/백준 2021. 8. 25. 16:29
[백준]18500: 미네랄 2 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 🪑 구현문제이다. 빡구현 문제. 풀이 방법이 정말 다향할 수 있는 문제라고 생각한다. 내 코드는 메모리 측면이나 코드 라인 측면이나 시간복잡도 측면에서 효율적이지 않은 코드이다. 하지만 다르게 최적화 할 방법이 떠오르지 않는다..ㅠㅠ 📝 문제를 정리해 보자! 왼쪽, 오른쪽에서 번갈아 막대기를 던진다. 막대기가 날아가다가 미네랄을 만나면 미네랄이 파괴되고 막대의 이동은 멈춘다. 미네랄이 파괴된 다음 공중에 뜨게 된 클러스터는 중력에 의해..
-
[백준]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이면 안된다. 위의 조건을 모두 만족하여 착륙지점에 착륙하는 경우의 수를 모두 구한다. 🙋♀️ 일단 점..