![]()
문제 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/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 문제 풀이 문제를 읽어보니 누적합의 최댓값을 구하는 문제라고 생각을 했다. DP 문제인줄 알았지만, 탐색하는 과정에서 시간이 오래 걸려서 투 포인터 알고리즘을 사용하기로 했다. 투 포인터 알고리즘을 사용했기 때문에 start와 end를 움직이면서 탐색을 진행한다. 기존의 투 포인터 문제들은 누적합을 넘어선 순간 start를 증가시키고, 누적합을 넘지 못한다면 end를 증..
![]()
문제 https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 문제 풀이 우선 내용이 굉장히 길고 문제를 이해하는데 너무 오래 걸렸던 문제이다. 만약 본인의 코드가 틀렸거나 막혔다면 내 해석이 도움이 되었으면 좋겠다. 우선 보드는 빨간색, 파란색, 초록색 3가지의 보드가 있다. 하나의 배열로 관리하는것이 아닌 3가지의 보드라는 클래스를 생성해서 관리하도록 했다. data class Block(val id: String) { lateinit v..
![]()
문제 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 문제 풀이 나는 해당 문제를 전형적인 bfs 문제라고 생각한다. 하지만 bfs 문제에서도 조금 더 진화한 문제이다. 우선 문제 초기에는 DP를 사용해서 주변에 존재하는 쓰레기를 저장해서 방문 처리를 하려고 했지만, 결과적으로 도착지점에 도착한 경우에 최적의 도착을 해야하기 때문에, 도착한 시점에 우리는 가장 적은 쓰레기를 마주치고 밟아야 한다. 그렇기 때문에 DP..
![]()
📕문제 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 🔎문제설명 bfs 문제에서 조금 변형이 있는 문제입니다. 스위치를 켜면 해당 방으로 이동할 수 있는 것이 아닌, 스위치를 켜고 스위치로 이동가능한지 여부를 판단해야 하는 문제입니다. 다른 bfs문제처럼 바로바로 큐에 넣는 것이 아닌 여부를 판단하고 큐에 넣어야 하기에 헷갈릴 여지가 있다고 생각합니다. 주의할 점은 (1,1)은 원래 불이 ..
![]()
문제 크기가 1 ×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 아래 그림은 H = 8, W = 7인 경우이고, 빈칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다. 7 . . . . . . . 7 . . . . . . . 6 . . . . . ..
![]()
문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 🔎문제 해석 원숭이의 동작수의 최소값을 구해야 하므로, BFS 알고리즘을 이용해서 출발지부터 도착지점까지 갈 수 있는지를 판단해야 합니다. 문제는 간단합니다. queue를 이용해서 좌표와 말처럼 이동한 횟수를 계속해서 기록해 둡니다. 만약 말처럼 이동한 횟수가 k-1 이하라면 말처럼 이동할 수 있습니다. 하지만 k이상이라면 말처럼 이동할 수 없습니다. 즉 queue에서 기록한..
![]()
문제 N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다. 모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다. 놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M..
