개발해요

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/1697

풀이

DP로 풀 수 있을 것 같았는데 방법이 떠오르지 않아서 우선 BFS를 사용했다. 매초마다 이전 위치들에서 도착할 수 있는 모든 위치로 움직이기 때문에 가장 처음 목표지점에 도착했을 때가 최단 시간이 된다.

또한, 곱하기2로 범위를 절반씩 줄일 수 있으므로 O(log^N) 시간으로 문제를 해결할 수 있다

BFS 과정에서 당연하지만 이전에 방문했던 점은 다시 방문하지 않아야 하는데, 이전보다 시간이 더 흐른 상태에서 같은 연산을 반복하기 때문이다. 따라서 방문표시를 할 배열이 필요한데, 크기를 어느 정도로 잡아야할지 고민이 됐다. 예를 들어 50,001 (x2) -> 100,002 (-1) (-1) -> 100,000 와 같이 최대 범위를 초과했다가 마이너스로 가는 경우도 있을 것 같았기 때문이다. 

결과적으로, 50,001 (-1) -> 50,000 (x2) -> 100,000처럼 최대 범위를 넘어서는 경우보단 숫자를 먼저 몇 번 빼고 x2를 하는게 항상 더 빨리 갈 수 있다. 그리고 절반인 50,000을 기준으로 숫자가 커질수록 그 차이는 훨씬 커진다.

ex)

1. 50,004 (x2) -> 100,008 (-8) -> 100,000 ==> 9번

2. 50,004 (-4) ->  50,000 (x2) -> 100,000 ==> 6번

따라서, 방문 가능 범위를 0 ~ 100,000으로 제한해도 문제를 해결할 수 있다.

개인적으로 처음엔 여기까지 생각하지 못해서 안전하게 최대 200,000까지 방문 가능하도록 했는데, 정답을 받을 수 있었다.

이후에 궁금해서 찾아봤는데, 최대 범위를 넘어서는 경우가 없는건 k의 최대 값이 짝수이기 때문이었다.

9 -> 15  ==>  9 -> 8 ->16 -> 15 의 케이스처럼, 최대 값이 홀수라면 최대 값을 넘어서고 마이너스로 가는 케이스가 존재할 수 있기 때문이다.

하지만 처음 문제를 풀 땐 생각하기 어려울 수 있기 때문에, 그럴 땐 범위를 충분히 안전하게 설정해서 푸는 게 좋을 것 같다.     

코드

import java.io.*
import java.util.*

// 250_000을 이상인 모든 수 n은
// (n * 2) 이후 -1씩 계산해주는 것보다
// -1을 먼저 몇 번 빼고 n * 2를 하는 게 항상 더 빠르다
// ex) 250_001 * 2 = 500_002 -> 500_000 ==> 3번 계산
// ex) 250_001 -> 250_000 -> 500_000 ==> 2번 계산
// 250_001에서 수가 커질 수록 차이는 더 커진다.
const val MAX_POSITION = 100_000

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val myPosition = input[0].toInt()
    val goal = input[1].toInt()

    val visited = BooleanArray(MAX_POSITION + 1)    // 방문 처리 배열
    val queue: Queue<Pair<Int, Int>> = LinkedList() // 위치, 지난 시간
    queue.offer(Pair(myPosition, 0))
    visited[myPosition] = true

    while (queue.isNotEmpty()) {
        val pair = queue.poll()
        val position = pair.first
        val time = pair.second

        if (position == goal) { // 동생을 찾았으면 종료
            print(time)
            return
        }

        // -1을 거쳐가는 최단경로는 존재할 수 없다
        val nextPosition1 = position - 1
        if (nextPosition1 >= 0 && visited[nextPosition1].not()) {
            visited[nextPosition1] = true
            queue.offer(Pair(nextPosition1, time + 1))
        }

        // 현재 위치가 동생의 위치보다 크면 증가 연산을 할 필요가 없다.
        if (position < goal) {
            val nextPosition2 = position + 1
            // 최대 범위를 넘었다가 왼쪽으로 가는 경로보다 더 빠른 경로가 항상 존재한다.
            if (nextPosition2 <= MAX_POSITION && visited[nextPosition2].not()) {
                visited[nextPosition2] = true
                queue.offer(Pair(nextPosition2, time + 1))
            }

            val nextPosition3 = position * 2
            if (nextPosition3 <= MAX_POSITION && visited[nextPosition3].not()) {
                visited[nextPosition3] = true
                queue.offer(Pair(nextPosition3, time + 1))
            }
        }
    }
}

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

난 아무래도 기하랑 도형에 약한 것 같다. 어려웠다..ㅋㅋ 도형만 나오면 시야가 좁아진다. 

처음에 직사각형 중 3개의 작은 직사각형의 합의 곱이라고 이해하고,  '한 두 개 점을 포함하지 않으면서 최대로 직사각형을 3개 만들 수 있는 방법도 있지 않을까' 싶었다. 상식적으론 모든 점을 다 포함해야 최대 값이 나올 것 같았지만, 수학의 세계는 혹시 모르니까..

어떻게 하는 걸까 고민하다가 다시 확인해보니 직사각형을 3개로 분할하는 문제였다.

풀이

직사각형을 3개로 분할할 수 있는 모양은 6가지가 있다.

이 각각의 형태에 대해 모든 크기를 확인해보면 최대값을 구할 수 있다.  

행렬을 표현하는 방법으로는 크게 2가지가 있다. (1) 한 점과 가로,세로 길이로 표현하는 방법과 (2)왼쪽 상단과 오른쪽 하단과 같이 양 끝의 두 점으로 표현하는 방법이다. 개인적으로 정사각형일 땐 (1)이 편하고 직사각형은 (2)가 편했다.

ex) 4번째 모양

이런 식으로 구성하면 한 줄짜리 행렬처럼 해당 모양을 만들 수 없을 땐, 반복문의 start, end 크기가 역전돼서 자동적으로 반복문이 실행되지 않는다.

코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val rowSize = input[0].toInt()
    val colSize = input[1].toInt()
    val square = Array<IntArray>(rowSize) {
        val numbers = readLine()
        IntArray(colSize) { i ->
            numbers[i] - '0'
        }
    }

    val lastRowIdx = rowSize - 1
    val lastColIdx = colSize - 1
    var answer = 0L

    // III
    for (col1 in 0 until colSize - 2) {
        for (col2 in col1+1 until colSize - 1) {
            val sum1 = getSquareSum(square, 0, 0, lastRowIdx, col1)
            val sum2 = getSquareSum(square, 0, col1+1, lastRowIdx, col2)
            val sum3 = getSquareSum(square, 0, col2+1, lastRowIdx, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // =
    for (row1 in 0 until rowSize - 2) {
        for (row2 in row1 + 1 until rowSize - 1) {
            val sum1 = getSquareSum(square, 0, 0, row1, lastColIdx)
            val sum2 = getSquareSum(square, row1+1, 0, row2, lastColIdx)
            val sum3 = getSquareSum(square, row2+1, 0, lastRowIdx, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // ㅜ
    for (row in 0 until rowSize - 1) {
        val sum1 = getSquareSum(square, 0, 0, row, lastColIdx)
        for (col in 0 until colSize - 1) {
            val sum2 = getSquareSum(square, row+1, 0, lastRowIdx, col)
            val sum3 = getSquareSum(square, row+1, col+1, lastRowIdx, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // ㅗ
    for (row in lastRowIdx downTo 1) {
        val sum1 = getSquareSum(square, row, 0, lastRowIdx, lastColIdx)
        for (col in 0 until colSize - 1) {
            val sum2 = getSquareSum(square, 0, 0, row-1, col)
            val sum3 = getSquareSum(square, 0, col+1, row-1, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // ㅏ
    for (col in 0 until colSize - 1) {
        val sum1 = getSquareSum(square, 0, 0, lastRowIdx, col)
        for (row in 0 until rowSize - 1) {
            val sum2 = getSquareSum(square, 0, col+1, row, lastColIdx)
            val sum3 = getSquareSum(square, row+1, col+1, lastRowIdx, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // ㅓ
    for (col in lastColIdx downTo 1) {
        val sum1 = getSquareSum(square, 0, col, lastRowIdx, lastColIdx)
        for (row in 0 until rowSize - 1) {
            val sum2 = getSquareSum(square, 0, 0, row, col-1)
            val sum3 = getSquareSum(square, row+1, 0, lastRowIdx, col-1)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    print(answer)
}

fun getSquareSum(square: Array<IntArray>, startRow: Int, startCol: Int, endRow: Int, endCol: Int): Long {
    var sum = 0L
    for (row in startRow..endRow) {
        for (col in startCol..endCol) {
            sum += square[row][col]
        }
    }

    return sum
}

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

풀이

골드5였는데 정말 정말 어려웠다.

지금껏 풀어봤던 문제들이랑 사고방식이 전혀 다르다는 느낌이 들었다. 구현이랑 완전 탐색 문제 경험이 부족한걸까.

처음에 그리디적으로 접근했는데 분기문이 감당이 안됐다. 브루트 포스 유형이란걸 알고나서도 어떻게 풀지 쉽게 떠오르지 않았다. 다른 분들 풀이를 참고했는데, 풀면서 멘탈이 나갔는지 처음엔 설명을 봐도 이해가 안됐다..ㅋㅋㅋ

알고나니까 컨셉은 간단했다!

버튼을 눌러서 한번에 이동할 수 있는 채널을 모두 구하는 것이다.

그러면, 모든 (이동 가능한 채널 i의 자리수) + (i에서 목표 채널 N(target)까지 거리) 중 최소 값과 100에서 N까지 +, -로 가는 거리 중 최소 값이 답이 된다.

순서

1. 고장난 버튼의 개수를 확인한다. 만약 버튼이 전부 고장났다면, +, -로 이동하는 횟수가 정답이다
2. 1개라도 고장나지 않았다면, 0 <= i <= 900,000에 대해, +, - 없이 i로 한번에 이동할 수 있는 수들을 확인한다.
3. 이동 가능한 수들의 i로 직접 버튼 클릭 + 절대값(N - i) 중 최소값을 구한다.
4. 위에서 구한 최소값과 100에서 N으로 곧장 가는 절대값(N - 100) 중 작은 값이 답이 된다. (N = 101 같은 케이스 고려)

900,000까지 탐색하는 이유는 다음과 같다.

문제가 원하는 답은 아래 3가지 경우 중 최소값이다

1. 100에서 N까지 바로 가는 경우
2. 100에서 i <= N인 i를 거쳐 가는 경우 (왼쪽에서 오른쪽)
3. 100에서 i > N인 i를 거쳐 가는 경우(오른쪽에서 왼쪽) 

그리고 2, 3번의 경우

• 왼쪽에서 오른쪽으로 가는 최대 횟수는 N = 500,000이고 고장나지 않은 버튼이 0인 경우의 100 -> 500,000인 499,900번,
• 오른쪽에서 왼쪽으로 가는 최대 횟수는 고장나지 않은 버튼이 0과 9인 경우의 100 -> 900,000 -> 500,000인 400,006번이다. 그 이상의 수를 확인해봤자 499,900번을 넘기 때문에 확인하지 않아도 된다.

좀 더 간단하게는 왼쪽 -> 오른쪽 최대 값이 약 50만이기 때문에 최대 숫자를 50만 + 50만 = 100만으로 설정해서,

0 <= i <= 1,000,000을 탐색할 수 있다!

코드1

import java.io.*
import java.util.StringTokenizer
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val target = readLine().toInt()
    val brokenCount = readLine().toInt()
    val broken = BooleanArray(10)

    // 버튼이 망가졌으면 true, 아니면 false
    if (brokenCount > 0){
        val st = StringTokenizer(readLine())
        repeat(brokenCount) {
            broken[st.nextToken().toInt()] = true
        }
    }

    // 전부 고장났으면 +, -로만 이동하는 게 정답
    if (brokenCount == 10 || target == 100) {
        print(abs(target - 100))
        return
    }

    // target = 101과 같은 경우 고려
    var minClicked = abs(target - 100)
    
    for (i in 0 until 900_000) {
        val number = i.toString()

        // i로 번호를 직접 입력해서 갈 수 있는지 확인한다.
        if (isReachable(number, broken)){
            val numberToTarget = abs(i - target) // i에서 target으로 +나-로 이동하는 횟수
            minClicked = min(minClicked, number.length + numberToTarget)
        }
    }

    print(minClicked)
}

// 각 자리수 중 하나라도 망가진 번호가 있으면 직접 거쳐갈 수 없다.
fun isReachable(target: String, broken: BooleanArray): Boolean {
    target.forEach{ ch ->
        val number = ch - '0'
        if (broken[number]) return false
    }

    return true
}

코드2 (각 자리수 확인할 때 문자열이 아닌 정수로 처리하는 버전)

import java.io.*
import java.util.StringTokenizer
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val target = readLine().toInt()
    val brokenCount = readLine().toInt()
    val broken = BooleanArray(10)

    if (brokenCount > 0){
        val st = StringTokenizer(readLine())
        repeat(brokenCount) {
            broken[st.nextToken().toInt()] = true
        }
    }

    if (brokenCount == 10 || target == 100) {
        print(abs(target - 100))
        return
    }

    var minClicked = abs(target - 100)
    for (i in 0 until 900_000) {
        val clickCount = getClickCount(i, broken)
        if (clickCount > 0){
            val iToTarget = abs(i - target)
            minClicked = min(minClicked, clickCount + iToTarget)
        }
    }

    print(minClicked)
}

fun getClickCount(target: Int, broken: BooleanArray): Int {
    var count = 0
    var targetNumber = target

    while(true) {
        val button = targetNumber % 10
        if (broken[button]) {
            return 0
        }

        count++
        targetNumber /= 10
        if (targetNumber == 0) break
    }

    return count
}