![]()
문제 https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 문제 풀이 오랜만에 풀어본 그리디 문제였다. 그리디문제는 문제에서 요구하는 최적의 결과를 도출하기 위한 접근방법을 잘 생각해야 하는 것 같다. 버스 정류장을 지날 때마다 2가지 선택지가 있다. 멈춰서 연료를 채우거나, 그냥 지나가거나 따라서 나는 모든 정류장을 지나갈 때마다 2가지 선택지를 우선순위큐에 넣어줬다. 이렇게 해도 괜찮을거라 생각했던 이유는 우..
![]()
문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 풀이 골드 1이라는 난이도답게 BFS와 여러 가지를 섞었던 문제였다. 우선 문제의 핵심은 주어진 섬을 모두 연결할 수 있는 다리를 건설하는데 발생하는 최소비용을 구하는 것이다. 해당 문구를 통해서 섬이라는 정점을 모두 연결해야 하는 MST라고 유추할 수 있다. 원래 MST는 모든 정점을 연결하는 문제이지만, 해당 문제는 정점을 확대한 섬으로 계산을 해야 했기 때문에..
![]()
문제 https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 문제 풀이 정말 오래 걸렸던 문제다. 특정 테케에서 통과하지 못해서 많이 고생했다. 내가 생각하는 알고리즘 분류는 조합과 BFS를 같이 사용하는 문제인 것 같다. 배양액을 뿌릴 수 있는 땅에 대해서 빨간색,초록색,배양액X에 조합을 통해서 경우의 수를 정해준다. 사용한 자료구조 private lateinit var setting: Se..
![]()
문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 문제 풀이 문제를 읽으면서 조건을 파악하고 차근차근 단계에 맞는 함수를 작성하면 되는 문제였다. 그 외에도 자료구조의 선택이 중요하다. 봄, 여름, 가을, 겨울에 맞는 동작을 구현해야 한다. 봄 private fun spring(): ArrayList { val aliveTrees = PriorityQueue(compareBy { it.age }) val deadTrees =..
![]()
문제 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 풀이 한마디로 요약하면 조건이 많은 그래프 탐색 문제이다. 내가 작성했던 메서드들은 크게 3가지로 분리된다. 가장 가까운 승객 찾기 private fun findGuest(): Triple? { val visit = Array(n) { BooleanArray(n) { false } } var result: Triple val pq = Priorit..
![]()
문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 풀이 문제를 풀기 위해서 생각해야 할 점은 외부 공기와 내부 공기의 분리를 어떻게 할 것인가 이다. 외부 공기와 내부 공기의 분리 외부 공기와 내부 공기의 다른 점은 어떤 것일까? 내가 생각한 점은 내부 공기는 치즈에 둘러싸여 밖으로 나가지 못하고, 외부 공기는 치즈에 둘러 쌓여 있지 않아서 자유롭게 움직일 수 있다는 점이다. 이를 구현하기 위해선 역발상이 필요하다. 내부공..
![]()
문제 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 문제 풀이 시물레이션을 연습하고 있는데, 정말 복잡한 것 같다. 문제가 정말 길고, 생각해야 될 케이스가 너무 많아서 굉장히 오래 걸렸다. 우선 문제의 중요 포인트는 다음과 같다. 원판 회전 원판 회전은 방향에 따라 달라진다. 행렬을 시계방향으로 옮겨주거나, 반시계방향으로 옮겨주는 것과 동일하다. private fun rotate(step: Int) { var temp = 0..
![]()
문제 https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 문제 풀이 문제가 길지만, 문제의 핵심은 M개의 보석을 연속적으로 주워야 한다는 사실이다. 핵심을 지키면서 주울 수 있는 보석의 최대값을 구하는 전형적인 누적합 문제이다. 나는 i번째의 보석을 이동할 때의 누적합을 accumulateSum 이라는 1차 배열로 잡았다. 따라서 accumulateSum[4]라면 4번째의 보석까지 이동했을 때의 누적합이다. 즉 여기는 1~4번째 보석의 ..
![]()
문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 처음 문제를 보고 이렇다 할 접근 방법이 떠오르지 않았다. 초기에는 하나의 원소를 기준으로 left를 고정시키고, right를 옮겨가면서 투포인터 알고리즘으로 합이 s가 되는 조합을 찾으려고 했었다. -7 -3 -2 5 8이 있을 경우 -7을 기준으로 오른쪽을 8로 고정시키고, 투포인터를 시작한다. 현재 포인터는 8이고, sum은 1이다. 합..
