문제 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 고슴도치가 비버의 굴로 이동하는 가장 빠른 시간을 찾는 문제로 BFS로 해결할 수 있다. 탐색에서 물이 차는 것도 고려해야하기 때문에 Queue를 물과 고슴도치 두 개를 이용하여 해결한다. 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없기때문에 한 싸이클을 물의 이동 -> 고슴도치의 이동의 순서로 구성하고 탐색을 수행한다. 물이나 고슴도치의 이동은 해당하는 현재 큐의 크기만큼 수행하고 빈공간을 만났을 때 이동한다. 고슴도치는 도착한 시간을 저장해주고 도착 지점에 ..

문제 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 입력받은 수열을 오름차순으로 정렬한 후, 두 포인터를 사용하여 원하는 합을 만드는 투 포인터 문제이다. 앞과 뒤에서 시작하는 두 개의 포인터를 조작하여 합을 조절하며 원하는 값에 도달하는데, 합이 목표값보다 크면 뒤의 포인터를 앞으로, 작으면 앞의 포인터를 뒤로 움직입니다. 두 포인터가 만날 때 반복문을 종료해준다. 투 포인터 알고리즘은 한 번의 루프마다 두 포인터 중 하나만 1씩 증가하며, 각 ..

문제 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 풀이 입력받은 두 자연수의 최대 공약수가 모든 자리가 1로만 이루어져있는 두 자연수의 최대 공약수의 자리수가 된다. 따라서 입력받은 수의 최대 공약수를 구하고 최대 공약수만큼 1을 출력해주면 된다. 예제 입력 2를 보면 3 과 6의 최대 공약수는 3이고 답은 111이다. 11111 = 111 x 1001로 나타낼수 있기 때문에 답은 맞다. 풀이가 왜 성립하는지의 증명은 https://www.acmicpc.net/board/view/32..

문제 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 문제에서 '누울 수 있는 자리에 몸을 쭉 뻗는다'는 조건이 있어서 헷갈릴 수 있다. 이 조건은 두 칸 이상의 빈 칸을 영식이가 누울 수 있는 하나의 공간이라는 의미이다. 예를 들어, 방의 상태가 "...X.." 인 경우 'X' 앞의 공간과 'X' 뒤의 공간으로 총 2개의 공간이 영식이가 누울 수 있는 공간이다. 이를 해결하기 위해 반복문을 통해 빈 칸을 확인하고 2칸이 될 때마다 갯수를 세어 준다. 'X'를 만날 때부터 빈칸을 다시 세어주는 ..

문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 Comparator를 활용하여 우선순위 큐를 내림차순으로 정의하고, 입력받은 숫자를 우선순위 큐에 저장한다. 그 후, N번째 큰 수를 출력해준다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val num = br.readLine().toInt() val pq = PriorityQueue(Comparator ..