개발해요

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

유형

정렬, 그리디 or 특정 알고리즘 X

풀이

풀이 순서

1. 일을 시작하는 시간(startTime)과 마지막 시간(endTime)으로 변환한다.

2. endTime이 가장 늦은(큰) 일부터 차례대로 최대한 늦게 일을 시작하도록 일의 시간을 확정 짓는다.

  => 따라서, 위 과정에 앞서 endTime 기준 내림차순으로 정렬한다.

3. 가장 빨리 시작하게 될 일의 startTime을 출력한다.

1. 일을 시작하는 시간(startTime)과 마지막 시간(endTime)으로 변환한다.

일을 시작하는 시간(startTime)과 마지막 시간(endTime)으로 변환한다.

ex) 걸리는 시간: 5, 끝내야 하는 시간 9 => endTime: 9 - 1 = 8, startTime: endTime - 5 + 1 = 4

이렇게 놓으면 endTime 바로 다음인 끝내야 하는 시간에 일이 끝나있게 된다.

data class Task(var start: Int, var end: Int)

repeat(taskSize) {
    val (duration, dueTime) = readLine().split(" ").map(String::toInt)
    taskList.add(Task(dueTime - duration, dueTime - 1))
}

2. endTime 값이 가장 큰 일부터 차례대로 최대한 늦게 일을 시작하도록 배치한다.

가장 늦게 일어나기 위해서 모든 일을 데드라인에 최대한 가깝게 배치하며, endTime 값이 가장 큰 task부터 스케줄을 확정한다. task(currentTask)를 스케줄할 때 직전에 배치한 task(nextTask)와 비교해서 타임 라인이 겹친다면, currentTask를 nextTask 바로 왼쪽으로 배치한다. 이렇게 하면 현재 상황에서 currentTask를 최대한 늦은 시간에 스케줄한 것이 된다.

ex) currentTask: task C, nextTask: task D

단, currentTask를 왼쪽으로 옮기는 과정에서 startTime < 0이 된다면, 제시간에 일을 끝낼 수 없다는 의미가 된다.

var prevTask = taskList[0]
for (i in 1 until taskSize) {
    val currentTask = taskList[i]

    // prevTask과 currentTask의 시간이 겹치는 부분이 있거나, 통째로 currentTask가 더 오른쪽에 있는 경우
    // -> currentTask를 겹치지 않게 왼쪽 옮긴다
    if (currentTask.end >= prevTask.start){ // currentTask가 prevTask에 걸쳐있는 경우
        val moveToLeftTime = currentTask.end - prevTask.start + 1
        currentTask.end -= moveToLeftTime
        currentTask.start -= moveToLeftTime
    }
    
    if (currentTask.start < 0) {
        print(-1)
        return
    }
    prevTask = currentTask
}

3. 가장 빨리 시작하게 될 일의 startTime을 출력한다.

위에서 수평선 기준 오른쪽에 있는 task부터 겹치지 않으면서 데드라인에 가깝게 배치하고 나면, 맨 왼쪽에 있는 task의 startTime이 일을 가장 늦게 시작할 수 있는 시간이 된다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader

// start: 일 시작 시간, end: 마지막 시간 -> end+1 시간에는 작업이 끝나있다 
data class Task(var start: Int, var end: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val taskSize = readLine().toInt()
    val taskList = mutableListOf<Task>()

    repeat(taskSize) {
        val (duration, dueTime) = readLine().split(" ").map(String::toInt)
        val task = Task(dueTime - duration, dueTime - 1)
        taskList.add(task)
    }

    // 가장 늦게 끝낼 일이 먼저 오도록 정렬
    taskList.sortByDescending { it.end } 

    // 비교 기준, 시간상 currentTask 바로 다음에 진행할 task
    var nextTask = taskList[0]
    
    for (i in 1 until taskSize) {
        val currentTask = taskList[i]

        // nextTask currentTask의 시간이 겹치는 부분이 있거나, 통째로 current가 더 오른쪽에 있으면
        // 겹치지 않게 current가 nextTask 직전에 끝나게 왼쪽으로 옮긴다
        if (currentTask.end >= nextTask.start){
            val moveToLeft = currentTask.end - nextTask.start + 1
            currentTask.end -= moveToLeft
            currentTask.start -= moveToLeft
        }

        // currentTask를 0초 이전에 시작해야 하면 -1 반환
        if (currentTask.start < 0) {
            print(-1)
            return
        }
        
        nextTask = currentTask // 비교 기준 갱신
    }

    print(taskList.last().start) // 가장 먼저 시작할 task의 시작 시간
}

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

안녕하세요, 이륙사입니다. 이번 게시물에서는 토너먼트 만들기 문제를 풀고 개인적으로 되돌아본 점을 기록했습니다.

핵심 아이디어

랭킹이 낮은(값이 큰) 선수들이 오래 남아 있을수록 랭킹 차의 합이 커진다.

왜냐면 토너먼트를 진행할수록 랭킹 값이 작은 선수들이 올라오기 때문에, 랭킹 값이 큰 선수들이 부전승으로 올라가면 항상 처음에 옆에 있던 선수들보다 랭킹 값이 같거나 작은 선수들과 맞붙게 된다.

ex) 1 4 2 5 3 7 - 랭킹차가 가장 작은 선수들부터 시합을 할 경우,

1 4 2 3 7 -> 1 4 2 7  -> 1 2 7 -> 1 2 -> 1 

만약 처음에 7과 3이 대결했다면 7에 의한 랭킹 차는 4로 끝났을 것이다.

따라서, 랭킹이 낮은 선수부터 우선적으로 게임을 진행시켜 떨어뜨린다.

회고

처음에 매 반복마다 랭킹 차가 작은 선수들부터 대결시키면 되겠구나 생각해서 틀렸다. 이후에 1 2 3 4 5 6 예시를 떠올리면서 랭킹차가 작은 선수들 중에서 값이 큰 선수들부터 대결시키면 되겠다 싶었는데, 그것도 아니었다.

사실 어떻게 위 아이디어를 떠올릴 수 있었을지 아직 잘 모르겠다.

랭킹 차이 합의 최소를 구한다 -> 위로 올라갈수록 랭킹이 높은 선수들이 남는다 -> 그들과 나중에 맞붙지 않도록 랭킹이 낮은 선수들을 먼저 떨어뜨린다.

이렇게 떠올릴 수 있었을까?

코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val rankings = MutableList(n) {
        st.nextToken().toInt()
    }

    print(getMinDiffSum(rankings))
}

fun getMinDiffSum(rankings: MutableList<Int>): Int {
    var sumOfDiff = 0 // 정답

    while (rankings.size > 1) {
        var maxRankIndex = 0

        // 랭킹이 가장 낮은(값이 큰) 선수를 찾는다
        for (i in 0 until rankings.size) {
            if (rankings[i] == rankings.size) {
                maxRankIndex = i
                break
            }
        }

        // 랭킹 차이가 더 작은 선수와 대결한다
        sumOfDiff += when {
            maxRankIndex == 0 -> abs(rankings[maxRankIndex] - rankings[maxRankIndex + 1])
            maxRankIndex == rankings.lastIndex -> abs(rankings[maxRankIndex] - rankings[maxRankIndex - 1])
            else -> min(
                abs(rankings[maxRankIndex] - rankings[maxRankIndex + 1]),
                abs(rankings[maxRankIndex] - rankings[maxRankIndex - 1])
            )
        }

        rankings.removeAt(maxRankIndex)
    }

    return sumOfDiff
}

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

안녕하세요, 이륙사입니다. 이번 게시물에서는 풍선 맞추기 문제의 풀이 과정을 복기하며 기록했습니다. 백준에서 그리디 알고리즘이라고 나와있지만, 개인적으로는 어떻게 단일 반복문으로 해결할 수 있을까에 대한 구현 문제에 가깝다고 느꼈습니다.

풀이 과정

먼저, 최소한의 화살을 사용하기 위해선 하나의 화살로 최대한 많은 풍선을 터뜨려야 합니다.

화살은 풍선을 하나 맞힐 때마다 높이가 1씩 감소하므로, 내림차순으로 높이가 1 차이나는 풍선들은 높이가 가장 큰 풍선에 화살을 한번 쏘는 것으로 그 풍선들을 모두 맞힐 수 있습니다. 

위의 예시의 경우, 3개의 화살(화살1(5, 4, 3), 화살2(5, 4, 3), 화살3(2, 1))로 풍선들을 전부 맞힐 수 있습니다.

접근

저는 먼저 이중 반복문으로 완전 탐색하는 방법을 떠올렸습니다. 앞에 있는 풍선에 화살을 쏘고, 뒤에 그 화살로 제거할 수 있는 풍선들이 있는지 확인하는 것입니다. 그럴려면 이중 반복문을 사용해야 하는데, 풍선이 최대 100만개라서 이 방법으론 시간 내에 해결이 불가능했습니다.

단일 반복문으로 줄일 수 있을까 고민하다가, 이중 반복문을 사용해도 날아가는 화살의 높이를 알고 있어야 한다는 점에 주목했습니다. 반복문으로 풍선들을 확인할 때 이때까지 쏜 화살 중 현재 확인하는 풍선의 높이로 날아오고 있는 화살이 있으면 쏘지 않고(저장x), 없으면 새로 쏘면 되겠다. 즉, 해싱(or 인덱스: 풍선 높이, 원소: 화살 개수)을 사용하면 단일 반복문으로 해결할 수 있겠다고 생각했습니다. 

val arrows = IntArray(MAX_HEIGHT + 1) // 날아가고 있는 화살을 높이에 따라 저장

balloons.forEach { height ->
    if (arrows[height] == 0) {  // height 높이에 날아오는 화살이 없으면
        count += 1              // 쏜다
        arrows[height - 1] += 1 // 풍선에 맞고 화살 높이 감소
    } else if (arrows[height] > 0) { // 날아오는 화살이 있으면
        arrows[height] -= 1          // 풍선에 맞는다
        arrows[height - 1] += 1
    }
}

코드

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

const val MAX_HEIGHT = 1_000_000

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val balloons = IntArray(n) {
        st.nextToken().toInt()
    }
    var count = 0
    val arrows = IntArray(MAX_HEIGHT + 1) // 날아가고 있는 화살을 높이에 따라 저장

    balloons.forEach { height ->
        if (arrows[height] == 0) {  // height 높이에 날아오는 화살이 없으면
            count += 1              // 쏜다
        } else if (arrows[height] > 0) { // 날아오는 화살이 있으면
            arrows[height] -= 1          // 풍선에 맞는다
        }

        arrows[height - 1] += 1 // 풍선에 맞고 화살 높이 감소
    }

    print(count)
}

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)
}