문제 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 풀이 행렬 A와 B를 반복문을 통해 비교한다. 만약 값이 다르다면 A 행렬을 해당 위치를 기준으로 3 x 3 부분 행렬을 뒤집고 횟수를 세어준다. 모든 연산을 마친 후 두 행렬이 다르다면 -1을 출력하고 같다면 뒤집은 횟수를 출력한다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val (rows, cols) = br.readLine().split(' '..

문제 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 풀이 입력받은 종이를 분할정복을 통해 처리하여 각 숫자(1, 0, -1)의 개수를 세는 문제이다. 입력받은 종이를 3X3 크기로 나누어 분할정복을 수행한다. 만약 현재 영역의 숫자가 모두 같다면 해당 숫자의 개수를 세고, 그렇지 않다면 3X3 영역을 다시 9개의 부분 영역으로 나누어 재귀적으로 처리한다. 이를 통해 종이 전체를 처리하면서 1, 0, -1의 개수를 각각 세어 결과를 출력한다. 코드 fun main() { val br = System..

문제 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 문제에서 주어진 집, 편의점, 페스티벌의 좌표를 그래프의 형태로 가공하여 BFS를 활용해 문제를 해결할 수 있다. 상근이는 매 50미터마다 맥주 한 병을 마셔야 하며, 최대 20병의 맥주를 들고 다닐 수 있다. 따라서 시작 위치에서 20 X 50 = 1000미터 이내라면 이동할 수 있는 지점이다. 이를 고려하여 집, 편의점, 페스티벌 장소를 각각의 정점으로 하고 정점 간의 거리가 1000미터 이내에 있으면 도착 가능한 거리라고 간주하여 그래프로 ..

문제 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 분할정복을 활용해 풀이하면된다. 데이터를 네 부분으로 나누어 재귀적으로 탐색하는데, 탐색할 때마다 괄호를 열고 닫아주면 된다. 같은 데이터로 이루어진 부분을 찾으면 해당 숫자를 출력해준다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val size = br.readLine().toInt() val arr = Array(s..

문제 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 분할정복이란 큰 문제를 작은 문제로 나누어 해결하는 재귀적인 알고리즘이다. 일반적으로 세 단계로 구성된다. - 분할(Divide): 주어진 문제를 더 작은 부분 문제들로 분할한다. 부분 문제들은 원래 문제와 동일한 형태를 가진다. - 정복(Conquer): 부분 문제들을 재귀적으로 해결하여 부분 해를 구한다. - 통합(Combine): 작은 부분 문제들의 해를 결합하여 원래 문제의 해를 구한다. 문제는 분할정복을 활용하여 종..