개발해요

https://www.acmicpc.net/problem/1038

프로세스

1. 재귀(백트래킹)를 사용해서 9에서 오른쪽 or 0에서 왼쪽으로 감소/증가 하는 방향으로 감소하는 수를 모두 구한다.
2. 오름차순으로 정렬한다.
3. n > 1023이라면 -1을, 그렇지 않다면 n번째 수를 출력한다.

풀이

처음엔 앞에 있는 수로 다음 수를 구하는 것 같아서 DP를 떠올렸지만 경우의 수가 아닌 n번째 수를 구하는 방법을 생각해내지 못했다.

다음은 완전 탐색으로 풀 수 있는지 생각해본다. 수의 범위: 0 ~ 9876543210, 하지만 이 숫자를 전부 확인하면 시간 초과다. 

어떻게 해야할까

각 자릿수는 일정한 방향성을 갖는다. 왼쪽의 수가 7이라면 오른쪽에 올 수 있는 수는 6~0이다. 이 아이디어에 착안하면 재귀적으로 감소하는 수만 골라서 모두 구할 수 있다. 그리고 이것을 정렬하면 n번째 감소하는 수를 구할 수 있다.

재귀 함수의 구체적인 구현은 다음과 같다

 1. 이전 수의 마지막 자리 숫자보다 작은 수를 오른쪽에 추가해서 새로운 숫자를 구한다. -> 나머지 연산 사용

 2. 새로 구한 숫자로 재귀 함수를 호출한다

for (i in lastDigit - 1 downTo 0) {
	val newNumber = number * 10 + i  // 오른쪽에 감소하는 수 추가
	addDecreasingNumber(newNumber)
}

 3. 호출된 함수는 숫자를 감소하는 수에 추가한다

 4. 마지막 자리 수가 0이라면 재귀 함수를 종료한다.

재귀 함수 소스 코드

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

위 방식은 왼쪽에서 오른쪽으로 숫자를 추가하면서 감소하는 방향으로 수를 구하고 있다. 반대로, 오른쪽에서 증가하는 방향으로 왼쪽에 숫자를 추가하는 방식도 가능하다.

감소하는 수를 구할 수 있을지 없을지는 어떻게 판단할까?

9 8 7 6 5 4 3 2 1 0에서 9531을 도출하는 방법을 경우의 수 관점에서 생각해볼 수 있다.

9, 5, 3, 1을 선택, 8, 7, 6, 4, 2, 0은 선택하지 않는 것이다. 각 자릿수를 선택/선택하지 않는 모든 경우의 수는 2^10개이고, 모두 선택하지 않는 경우는 없기 때문에 2^10 - 1 = 1023 개가 나온다. 따라서, n > 1022라면 감소하는 수를 구할 수 없다.

코드 (Kotlin)

1. 감소하는 방향으로 백트래킹

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val targetIndex = readLine().toInt()

    if (targetIndex <= 10) {
        println(targetIndex)
    } else if (targetIndex >= 1023){ // 감소하는 수의 개수는 1023개다
        println(-1)
    } else {
        for (i in 0..9) {
            addDecreasingNumber(i.toLong())
        }
        decreasingNumbers.sort()
        println(decreasingNumbers[targetIndex])
    }
}

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

2. 증가하는 방향 

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()
    
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val targetIndex = readLine().toInt()

    if (targetIndex <= 10) {
        println(targetIndex)
    } else {
        addDecreasingNumber(0, 0, 0)
        decreasingNumbers.sort()

        if (targetIndex > decreasingNumbers.lastIndex) {
            println(-1)
        } else {
            println(decreasingNumbers[targetIndex])
        }
    }
}

fun addDecreasingNumber(startNumber: Int, beforeLength: Int, beforeNumber: Long) {
    if (beforeLength >= 10 || startNumber >= 10) {
        return
    }

    for (i in startNumber..9) {
        val newNumber = i * (10.0).pow(beforeLength).toLong() + beforeNumber
        decreasingNumbers.add(newNumber)
        addDecreasingNumber(i + 1, beforeLength + 1, newNumber)
    }
}

https://www.acmicpc.net/problem/13397

안녕하세요, 이륙사입니다.

어제 백준에서 구간 나누기2 문제를 풀어봤습니다. 이전에 풀어본 유형이어서 알고리즘은 떠올랐지만 구체적인 풀이법이 떠오르지 않더라구요. 왜 그렇게 풀어야했는지 제대로 이해하지 못하고 넘어갔던 것 같아서 이번 기회에 정리해보려고 합니다.

선 정리

1. 구간을 어떻게 나눌까 -> 반대로 접근해서 구간 점수의 최대값을 기준으로 구간을 나눌 수 있는지 확인한다. -> 이분 탐색
2. 점수 최대값의 범위: 0 ~ (배열 최대값 - 최소값)
3. 구간을 나눌 때, 구간마다 최대한 길게 만든다 -> M개 이하가 될 확률을 높일 수 있음
   1. M개 이하로 나누는데 성공 -> 더 점수를 낮춰도 나눌 수 있는지 확인 -> upper = mid - 1
   2. M개 이하로 나누는데 실패 -> 점수를 더 높여서 확인 -> lower = mid + 1  
   3. 왜? 우리의 목표는 점수 최대 값의 최소값을 구하는 것이며, 구간 당 가능한 점수가 클수록 구간의 길이가 길어질 확률이 높아지기 때문이다. 

후 풀이

언뜻 읽어보면 점수의 최댓값의 최솟값, 말이 좀 복잡해 보입니다. 저는 구간을 나누면 점수가 계산되고 그 중 최댓값이 존재할텐데, 그 최댓값을 최소로 만들고 싶다. 즉, '구간을 어떻게 나눠야 가장 작은 (점수 최댓값: maxScore)을 구할 수 있을까'라고 이해했습니다. 

어떻게 구간을 나눠야 최소값을 얻을 수 있을까에 대한 문제구나 생각하고, 완전 탐색을 먼저 떠올렸습니다. 하지만 M개 이하로 나누기 때문에 시간 복잡도가 팩토리얼 수준으로 나와서 불가능하다고 판단했습니다.

반대로 접근한다

어떻게 해결할 수 있을까,,, 결론적으로 반대로 접근해서 해결할 수 있는 문제였습니다. 즉, 점수 최댓값을 먼저 설정하고, 그걸 기준으로 M개 이하의 구간을 나눌 수 있는지 확인하는 겁니다. 그 과정에서 이분 탐색을 사용합니다.

1. 점수 최대값의 범위는 배열이 하나일 때의 최소값 0에서 배열 내 최대값과 최소값의 차이 즉, 0 ~ (max(array) - min(array))입니다.
2. 이제 점수 (최대값)을 기준으로 구간을 나눠봅니다. 구간마다 최대한 많은 길이를 차지하도록 만듭니다. 왜냐면,
   1. M개 이하로 구간을 나눠야하기 때문에 구간을 최대한 길게 만들수록 성공 확률이 높아집니다.
   2. 앞의 구간에서 최대한 많은 숫자를 가져갈수록, 뒤에 남은 숫자들의 범위가 작아집니다. 그러면 그만큼 뒤에 구간의 점수도 작아질 확률이 높아집니다.
3. M개 이하로 구간을 만들지 못했다면, 점수를 더 크게 해서 구간을 나눌 수 있는지 다시 확인합니다. 반대로 성공했다면, 점수를 더 작게 해도 구간을 나눌 수 있는지 확인합니다. 이렇게 기준을 잡을 수 있는건, 점수가 클수록 구간이 길어질 확률이 높아지기 때문입니다. 즉, 평균적으로 구간마다 더 많은 숫자를 가질 수 있게 됩니다. 그리고, 우리의 목표는 점수 최대값의 최소값을 구하는 것이니까요!

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    // 입력
    val (n, divideLimit) = readLine().split(" ").map(String::toInt)
    val array = with(StringTokenizer(readLine())){
        IntArray(n){
            this.nextToken().toInt()
        }
    }
    
    var lower = 0
    var upper = array.maxOrNull()!! - array.minOrNull()!!

    if (n == 1) { // 배열 크기가 하나일 때
        print(0)
        return
    } else if (divideLimit == 1) { // 구간 1개 -> 배열을 나눌 수 없을 때
        print(upper - lower)
        return
    }

    // 점수의 최대값을 기준으로 이분 탐색
    // 점수의 최댓값이 mid가 되도록 구간을 가장 길게 나눠본다
    // 나눌 수 있으면 최소값을 찾기 위해 더 작은 최대값을 찾아본다
    // 나눌 수 없으면 더 큰 최대값을 찾는다
    // 구간의 점수가 커질수록 구간이 길어지고 구간 개수가 작아질 확률이 높아진다 
    while (lower <= upper) {
        val mid = (lower + upper) / 2

        if(isValid(array, mid, divideLimit)) {
            upper = mid - 1
        } else {
            lower = mid + 1
        }
    }

    print(lower)
}

fun isValid(array: IntArray, standard: Int, divideLimit: Int): Boolean {
    var count = 0
    var max = 0
    var min = 10_001

    for (i in array.indices) {
        max = max(max, array[i])
        min = min(min, array[i])

        // 최대값 or 최소값이 더 크/작아져서 더 길게 나눌 수 없을 때
        if (max - min > standard) {
            count++
            max = array[i]
            min = array[i]
        }
    }
    count++ // 마지막 구간

    return count <= divideLimit
}

후기

어떻게 생각하면 풀 수 있다는 건 확실히 알게됐지만, 왜 이렇게 접근해야만 하는지는 사실 아직도 와닿지가 않습니다. 이렇게 접근할 수도 있다는 걸 숙지하고, 사고의 폭을 넓혀가야 하는 걸까요? 조금은 답답하기도 한데, 이와 관련해서 댓글로 남겨주신다면 정말 감사하겠습니다.

https://www.acmicpc.net/problem/13164

안녕하세요, 이륙사입니다.

풀이

위 문제는 비용이 키 차이와 관련있다는 사실에서부터 시작하는 문제였습니다.

인접한 원생들의 키 차이를 값으로 갖는 새로운 수열을 구합니다. 그리고 그 수열의 합에서 값이 가장 큰 k-1개의 값을 빼면 그것이 정답이 됩니다. 왜냐하면 (큰 키 - 작은 키)의 값은 그 사이에 있는 원생들간 키 차이의 합과 같기 때문입니다. 그리고 아래 예시처럼 조를 k개로 나누면 k-1개의 경계가 생기며, 그 경계에 해당하는 차이 값들만 비용을 계산하는데 사용되지 않습니다. 따라서, 전체 차이의 합에서 가장 큰 k-1개를 빼주면 그것이 답이 됩니다.

예)

7, 3

1 3 5 6 10 16 19

또한, 전체 값의 합에서 가장 큰 값들을 빼주기 때문에 그리디 유형의 문제라고 할 수 있습니다. 

생각 과정

1. 학생 수가 최대 300,000이므로, 전부 확인해볼 순 없다.
2. 비용은 조에서 가장 키가 큰 학생과 가장 작은 학생의 차이다 --> 값의 차이에 주목한다.
3. 인접 원소들간 차이에 대해서도 생각해볼 수 있다.
4. 가장 키가 큰 학생과 작은 학생의 키 차이는 두 학생 사이에 있는 학생들간 키 차이의 합이란 것을 발견한다.
5. 조를 나누어본 결과, 비용의 합은 전체 키 차이의 합에서 가장 큰 k-1개의 값을 뺀 값이라는 것을 확인한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.sqrt

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, k) = readLine().split(" ").map{ it.toInt() }
    val st = StringTokenizer(readLine())
    val gaps = IntArray(n) { st.nextToken().toInt() }
    
    // 인접 학생간 키차이를 값으로 갖는 수열
    for (i in 0 until n-1) {
        gaps[i] = gaps[i+1] - gaps[i]
    }

    // k개로 나누면 k-1개의 경계가 생긴다
    gaps.sort() // 전체에서 값이 큰 경계 k-1개를 빼기 위해 먼저 정렬한다  
    
    // 가장 큰 k-1개를 뺀 나머지를 모두 더한다
    val min = (0 until (n-1)-(k-1)).sumOf { i -> gaps[i] }
    print(min)
}

https://www.acmicpc.net/problem/1517

풀이

크게 2가지의 풀이 법이 있다. 그 중 좀 더 쉬운 방법이 분할 정복법인데, 그것도 아이디어를 떠올리기가 쉽지 않은 것 같다. 그래서 다른 분들의 풀이와 코드를 많이 참고했다.

먼저, 수가 최대 50만개라서 버블 소트를 쓰면 시간 초과가 난다.

각 숫자가 몇 번 swap 되는지를 그림으로 알아보면 다음과 같다.

각 숫자의 교점의 합이 총 swap의 합이 된다. 그리고 각 숫자의 교점의 개수는 자신보다 오른쪽에 있는 숫자들 중 더 작은 수의 개수가 된다. 예를 들어, 위의 6은 1, 3, 5 => 3번 swap 한다.

그러면 어떻게 O(n^2)보다 빠르게 각 숫자들의 오른쪽을 탐색할 수 있을까? Merge Sort를 하면 merge sort의 시간 복잡도인 O(n * log^n) 안에 가능하다.

위의 그림은 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]
    }
}