"이동 방식을 모두 한 번씩 사용해서 움직일 수 있도록 체스판이 주어졌다면, 최소한 모든 방법을 1번 씩은 사용해야 한다. 만약 모든 방식을 사용할 수 없다면, 4번 이상 움직일 수 있더라도 3번 이하로 움직인다.
방법 하나를 사용할 때마다 한 번 움직인 것이며, 시작 지점도 방문한 것으로 간주한다. 위의 조건을 만족하는 최대 방문 횟수를 구하여라."
이동 방식을 모두 사용할 수 있는 경우와 없는 경우는 어떻게 나눌 수 있을까?
1. 모두 사용할 수는 없는 경우
1) 세로 길이 == 1
이동 방식을 살펴보면 가장 왼쪽 아래에서 시작해서 오른쪽으로만 이동하며, 위나 아래로 함께 움직여야 한다.
따라서 세로 길이가 1이면 가로가 아무리 길어도 움직일 수 없다.
=> 최대 방문 횟수 = 0
2) 세로 길이 == 2
위 아래로 두 칸씩 올라가는 방법이 있기 때문에,세로 길이가 2이면 위나 아래로 두 칸 이동하는 방법은 사용할 수 없다. =>최대 방문 횟수 = min(4, (세로 길이 + 1) / 2)
3) 세로 >= 3 && 가로 < 7
M < 7
세로가 3이상이더라도 모든 방법을 사용할 수 있는 건 아니다. 모든 방법을 한 번씩 사용하면 항상 가로 방향으로 6번을 움직이기 때문이다. 따라서, 가로 길이가 7 미만이면 세로가 아무리 길어도 모든 방법을 사용할 수 없다. 세로가 3이상일 때 가장 많이 움직일 수 있는 방법은 오른쪽으로 한 칸씩만 이동하는 것이기 때문에
=> 최대 방문 횟수 = min(4, 가로 길이)
2. 모두 사용할 수 있는 경우 - 세로 >= 3 && 가로 >= 7
N >= 3 && M >= 7
이제 적절히 순서를 조합해서 모든 방법을 다 사용할 수 있다. 모든 방법을 한 번씩 다 사용하고 나면, 오른쪽으로 가장 많이 방문할 수 있도록 움직여서 최대 방문 횟수를 구할 수 있다.
=> 최대 방문 횟수 = 5 + (가로 길이 - 7)
일반 구현 문제였지만 지문이 이해하기 어렵고 분기문이 많아서 쉽지 않았던 것 같네요!
코드
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val input = readLine().split(" ")
val rowLength = input[0].toInt()
val colLength = input[1].toInt()
when{
// 모든 조건을 한번씩 사용할 수 없을 땐
// 3번 이하로만 움직여서 방문 횟수를 4번 이하로 만든다.
rowLength == 1 -> print(1)
rowLength == 2 -> {
val visitCount = (colLength + 1) / 2
print( if(4 < visitCount) 4 else visitCount )
}
// 모든 조건을 한번 씩 써서 움직이면 가로로 6칸 이동하기 때문에
// 가로 길이는 7이 기준이 된다.
colLength < 7 -> print( if(4 < colLength) 4 else colLength)
// 모든 조건을 한번씩 사용해서 움직일 수 있으므로
// (한번씩 사용해서 방문한 횟수: 5) + (남아있는 가로 칸에서 가장 많이 움직일 수 있는 횟수)
else -> print(5 + colLength - 7)
}
}
크게 2가지의 풀이 법이 있다. 그 중 좀 더 쉬운 방법이 분할 정복법인데, 그것도 아이디어를 떠올리기가 쉽지 않은 것 같다. 그래서 다른 분들의 풀이와 코드를 많이 참고했다.
먼저, 수가 최대 50만개라서 버블 소트를 쓰면 시간 초과가 난다.
각 숫자가 몇 번 swap 되는지를 그림으로 알아보면 다음과 같다.
각 숫자의 교점의 합이 총 swap의 합이 된다. 그리고 각 숫자의 교점의 개수는 자신보다 오른쪽에 있는 숫자들 중 더 작은 수의 개수가 된다. 예를 들어, 위의 6은 1, 3, 5 => 3번 swap 한다.
그러면 어떻게 O(n^2)보다 빠르게 각 숫자들의 오른쪽을 탐색할 수 있을까? Merge Sort를 하면 merge sort의 시간 복잡도인 O(n * log^n) 안에 가능하다.
merge sort
위의 그림은 merge sort를 하는 과정에서 가장 작은 0을 정렬한 다음 상황이다.
이제 왼쪽에서 가장 작은 2와 오른쪽에서 가장 작은 1 중 더 작은 값을 정렬해야 한다. 오른쪽 값이 더 작기 때문에 1을 정렬한다. 그리고 그 과정에서 1이 2,4,6,8과 교차되는 것을 알 수 있다. 즉, 1은 2, 4, 6, 8과 swap이 되고, swap += (왼쪽 배열 개수 - 왼쪽 인덱스)와 같은 방식으로 swap 횟수를 계산할 수 있다. 이러한 과정은 오른쪽 최소 값이 왼쪽 최소값보다 작을 때마다 적용된다.
참고로 swap 횟수는 최악의 경우 대략 50만 + ... + 1 => 50만 * 50만이 될 수 있기 때문에 Long형을 사용해야 한다!
코드
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
var count = 0L
lateinit var tempArray: IntArray
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val st = StringTokenizer(readLine())
val numbers = IntArray(n) { i ->
st.nextToken().toInt()
}
tempArray = IntArray(n)
mergeSort(numbers, 0, n-1)
print(count)
}
fun mergeSort(numbers: IntArray, start: Int, end: Int) {
if (start == end) {
return
}
val mid = (start + end) / 2
mergeSort(numbers, start, mid)
mergeSort(numbers, mid + 1, end)
merge(numbers, start, end) // 정렬된 양쪽 배열을 합치면서 다시 정렬한다
}
fun merge(numbers: IntArray, start: Int, end: Int) {
val mid = (start + end) / 2
var left = start
var right = mid + 1
var tempIndex = start
while(left <= mid && right <= end) {
// 꼭 등호는 왼쪽이 더 작거나 같은 조건으로 붙여야 한다.
// 그렇지 않으면 왼쪽과 오른쪽 값이 같을 때 1을 더 계산하게 된다.
if (numbers[left] <= numbers[right]){
// 왼쪽 값이 더 작거나 같다 -> 오른쪽 배열에 자신보다 큰 값이 없다
tempArray[tempIndex++] = numbers[left++]
}else{
tempArray[tempIndex++] = numbers[right++]
count += mid - left + 1
}
}
// 왼쪽이나 오른쪽 중 남아있는 배열의 숫자 정렬
while (left <= mid) {
tempArray[tempIndex++] = numbers[left++]
}
while (right <= end) {
tempArray[tempIndex++] = numbers[right++]
}
// 임시 배열에 정렬한 값을 원래 배열에 반영
for (i in start..end) {
numbers[i] = tempArray[i]
}
}
(3^k)꼴의 N과 3x3 패턴의 출력 형식이 주어졌을 때, 그 패턴에 맞춰 NxN 크기로 별을 출력하는 문제였다.
NxN은 (N/3) x (N/3) 크기의 영역 9개로 이루어져 있으며, 그 나누어진 영역은 다시 9개의 더 작은 영역으로 이루어져 있다. 그래서 문제에서 주어진 것처럼, 재귀적인 분할 정복 방식을 사용하여 문제를 해결할 수 있다.
9x9 = (3x3) 9개
위 그림은 N = 9일 때를 나타낸 것이다. 만약 N = 27이라면 이 그림이 9개로 이루어져 있을 것이다.
즉, NxN을 그리기 위해선 (N/3) x (N/3) 9개를 그려야 하고, N/3을 다시 나누다 보면 결국 3x3 영역부터 그리기 시작해서 전체를 그리게 된다.
참고로 영역은 배열을 사용하여,
가장 왼쪽 상단의 시작점(row, col)과 영역의 크기(size)를 통해 영역을 나타낼 수 있다.
배열, 시작점, 크기로 영역을 나타낼 수 있다
그러면 이제 NxN 패턴의 별을 그리는 재귀 함수를 선언하고, 그 안에서 크기가 3이 될 때까지 (N/3) x (N/3) 영역 9개 그리도록 재귀적으로 호출하면 문제를 해결할 수 있다.
위의 과정에서 영역을 인자로 받아서 3x3패턴의 별을 배열에 저장해주는 함수와 공백을 저장하는 함수가 추가적으로 필요하다.
시작점: (row, col), 크기: size인 별을 그리는 함수
풀이2
풀이1은 영역을 중심으로 분할해서 가장 작은 단위부터 해결하는 방식이었다. 다른 방법은 없을까 궁금해서 다른 분들의 풀이를 살펴보다가, 같은 분할 정복이지만 약간 다른 관점의 방법이 있어서 소개하려고 한다.
이 방법도 어느 영역에 속하는지가 중요하긴 하지만, 영역 자체가 아닌 각 점이 어느 영역에 속하는지 판단하여 해당 위치에 '*' 이나 ' '를 저장한다.
3x3의 빈칸
우선, 기본 단위인 3x3에서 빈칸은 각 정사각형의 1행 1열에 해당한다. 좌표는 (1,1), (1, 4), (1, 7), (1, 10), (1, 13)이며,
판별식은 (i % 3 == 1) && (j % 3 == 1)이다.
9x9에서도 1행 1열이 공백에 해당한다
9x9 패턴에서도 공백은 3x3 단위로 봤을 때 1행 1열 영역에 해당한다.
즉, N x N 패턴에서 1행 1열에 있는 (3/N) x (3/N) 영역 전부가 공백에 해당한다.
그리고 모든 크기로 확장한 판별식은 {(i / size) % 3} == 1 && {(j / size) % 3} == 1이 된다.
i / size 은 그 점이 3*size x 3*size 단위로 봤을 때, 몇 번째 행의 size x size 영역인지를 나타낸다.
예를 들어 N = 27, size = 9, i = 11, j = 0이라면,
27x27의 일부분
i / (size/3) = 3이므로 위에서 네 번째 3x3 영역에 속하며,
3 % 3 = 0이므로 9x9 영역에서 0행 0열에 있는 3x3에 속한다. 즉 1행 1열이 아니기 때문에 공백이 아닌걸 알 수 있다.
그리고 이것을 재귀적 코드로 나타내면 아래와 같다.
코드1
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val stars = Array(n) { CharArray(n) }
setStars(stars, 0, 0, n) // NxN 패턴 별을 그린다
val answer = StringBuilder()
stars.forEach { charArray ->
charArray.forEach {
answer.append(it)
}
answer.appendLine()
}
print(answer)
}
// 왼쪽 위의 점인 stars[row][col]에서부터 size * size만큼 별 저장
fun setStars(stars: Array<CharArray>, row: Int, col: Int, size: Int) {
// 크기가 3일 때까지 나누어 들어가다가, 3이 되면 해당 영역에 3x3 패턴을 저장하고 종료한다.
if (size == 3) {
set3Pattern(stars, row, col, size)
return
}
val dividedSize = size / 3
// 0행
setStars(stars, row, col, dividedSize)
setStars(stars, row, col + dividedSize, dividedSize)
setStars(stars, row, col + 2*dividedSize, dividedSize)
// 1행
setStars(stars, row + dividedSize, col, dividedSize)
setSpace(stars, row + dividedSize, col + dividedSize, dividedSize) // 공백
setStars(stars, row + dividedSize, col + 2*dividedSize, dividedSize)
// 2행
setStars(stars, row + 2*dividedSize, col, dividedSize)
setStars(stars, row + 2*dividedSize, col + dividedSize, dividedSize)
setStars(stars, row + 2*dividedSize, col + 2*dividedSize, dividedSize)
}
// 3 * 3 패턴 별 저장
fun set3Pattern(stars: Array<CharArray>, startRow: Int, startCol: Int, size: Int) {
for (row in startRow until startRow + size){
for (col in startCol until startCol + size){
stars[row][col] = '*'
}
}
stars[startRow + 1][startCol + 1] = ' '
}
// 공백 저장
fun setSpace(stars: Array<CharArray>, startRow: Int, startCol: Int, size: Int) {
for (row in startRow until startRow + size){
for (col in startCol until startCol + size){
stars[row][col] = ' '
}
}
}
코드2
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val answer = StringBuilder()
for (i in 0 until n) {
for (j in 0 until n) {
answer.append(getStar(i, j, n / 3)) // 위치에 해당하는 '*' or ' ' 반환
}
answer.appendLine()
}
print(answer)
}
fun getStar(row: Int, col: Int, size: Int): Char {
// 해당 위치가 (3*size) * (3*size)의 정사각형 영역 안에서,
// 가운데 영역인 (size * size) 정사각형 안에 포함될 경우
if ((row / size) % 3 == 1 && (col / size) % 3 == 1){
return ' '
}
return if (size == 1) '*'
else getStar(row, col, size / 3)
}
