개발해요

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

생각 과정

1. 문제 재해석: 앞, 뒤 순서를 만족시키되 연속 상관없이 숫자들을 선택해서 더했을 때 값이 S가 되는 경우의 수를 구하시오
2. 모든 경우의 수를 확인한다면 2^40가지가 나오기 때문에 시간 내에 해결할 수 없다.
3. 수열을 절반으로 나누면 2^20가지이므로 각각의 부분합은 모두 구할 수 있다.
4. 합 S가 정해져 있으므로, 한쪽 부분합 배열에서 숫자를 선택하면 다른 한쪽에 존재하는지 확인할 숫자가 정해진다.
5. 한쪽의 부분합을 순회하면서 다른 한쪽에 원하는 숫자가 있는지 찾는다 -> 해싱, 투포인터, upper_bound - lower_bound를 사용해서 해결할 수 있다.
6. 피자 판매(https://www.acmicpc.net/problem/2632)와 비슷한 문제였다. (피자 판매 포스팅: https://best-human-developer.tistory.com/60) 

코드 (해싱)

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

lateinit var numbers: IntArray
val leftSumCount: MutableMap<Int, Int> = HashMap()
var goal = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, mGoal) = readLine().split(" ").map(String::toInt)
    val st = StringTokenizer(readLine())
    numbers = IntArray(n) { st.nextToken().toInt() }
    goal = mGoal

    recordLeftSum(0, 0)
    val answer = countAnswer(n / 2, 0)

    if (goal == 0) print(answer - 1) // 각 구간에서 아무것도 뽑지 않아서 0이 된 경우를 뺀다
    else print(answer)
}

// 왼쪽 절반 구간에서 구할 수 있는 모든 부분수열의 합을 key, 개수를 value로 Map에 저장한다
fun recordLeftSum(idx: Int, sum: Int) {
    if (idx >= numbers.size / 2) {
        leftSumCount[sum] = leftSumCount.getOrDefault(sum, 0) + 1
        return
    }

    recordLeftSum(idx + 1, sum)
    recordLeftSum(idx + 1, sum + numbers[idx])
}

// 오른쪽 구간 부분수열의 합(rightSum)을 모두 구해서,
// 자신과 합했을 때 목표 숫자를 만드는 leftSum의 개수를 Map에서 찾아서 반환한다
fun countAnswer(idx: Int, sum: Int): Long {
    if (idx >= numbers.size) {
        return leftSumCount.getOrDefault(goal - sum, 0).toLong()
    }

    return countAnswer(idx + 1, sum) + countAnswer(idx + 1, sum + numbers[idx])
}

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

안녕하세요, 이륙사입니다. 이번 게시물에서는 주사위 굴리기 문제를 풀고 개인적으로 되돌아볼 점을 정리했습니다.

중요 포인트

1. 3차원의 주사위를 1차원의 배열로 표현한다. 

val dice = IntArray(6) // 위, 바닥, 동, 서, 남, 북

인덱스를 특정한 면으로 가정한다.

2. 굴릴 때마다 방향에 맞게 주사위의 상태를 변경한다.

fun moveDice(dice: IntArray, cmd: Int) {
    when(cmd) {
        1 -> moveEast(dice)
        2 -> moveWest(dice)
        3 -> moveNorth(dice)
        else -> moveSouth(dice)
    }
}

fun moveEast(dice: IntArray) {
    val temp = dice[0]

    dice[0] = dice[3]
    dice[3] = dice[1]
    dice[1] = dice[2]
    dice[2] = temp
}

지문 해석이 어렵게 느껴졌던 이유

1. 문제를 재정의하지 않았다. -> 문제를 확실히 이해하지 않고 풀이부터 시도했다
2. 전개도가 왜 주어졌는지 모른채, 전개도대로만 문제를 바라보려고 했다.

코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    val rowSize = st.nextToken().toInt()
    val colSize = st.nextToken().toInt()
    var row = st.nextToken().toInt()
    var col = st.nextToken().toInt()
    val cmdSize = st.nextToken().toInt()

    val graph = Array(rowSize) {
        st = StringTokenizer(readLine())
        IntArray(colSize) {
            st.nextToken().toInt()
        }
    }

    
    val dice = IntArray(6) // 위, 바닥, 동, 서, 남, 북
    val answer = StringBuilder()
    st = StringTokenizer(readLine())
    val dRow = intArrayOf(0, 0, 0, -1, 1)
    val dCol = intArrayOf(0, 1, -1, 0, 0)

    for (i in 0 until cmdSize) {
        val cmd = st.nextToken().toInt()
        val nextR = row + dRow[cmd]
        val nextC = col + dCol[cmd]
        
        if (nextR !in 0 until rowSize || nextC !in 0 until colSize) {
            continue
        }

        moveDice(dice, cmd)

        if (graph[nextR][nextC] == 0) {
            graph[nextR][nextC] = dice[1]
        } else{
            dice[1] = graph[nextR][nextC]
            graph[nextR][nextC] = 0
        }

        row = nextR
        col = nextC
        answer.append(dice[0]).appendLine()
    }

    print(answer)
}

fun moveDice(dice: IntArray, cmd: Int) {
    when(cmd) {
        1 -> moveEast(dice)
        2 -> moveWest(dice)
        3 -> moveNorth(dice)
        else -> moveSouth(dice)
    }
}

fun moveEast(dice: IntArray) {
    val temp = dice[0]

    dice[0] = dice[3]
    dice[3] = dice[1]
    dice[1] = dice[2]
    dice[2] = temp
}

fun moveWest(dice: IntArray) {
    val temp = dice[0]

    dice[0] = dice[2]
    dice[2] = dice[1]
    dice[1] = dice[3]
    dice[3] = temp
}

fun moveNorth(dice: IntArray) {
    val temp = dice[0]

    dice[0] = dice[4]
    dice[4] = dice[1]
    dice[1] = dice[5]
    dice[5] = temp
}

fun moveSouth(dice: IntArray) {
    val temp = dice[0]

    dice[0] = dice[5]
    dice[5] = dice[1]
    dice[1] = dice[4]
    dice[4] = temp
}