개발해요

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

안녕하세요, 이륙사입니다. 제가 요새 종만북을 보고 있는데, 알고스팟은 코틀린을 지원하지 않아서 비슷한 문제를 찾다가 발견했습니다. 결론적으로 완전히 같은 문제는 아니었지만 비슷해서 도움이 많이 됐어요!

풀이

이 문제는 재귀(백트래킹)를 사용하는 완전 탐색 문제였습니다.

단순 조합으로 생각해보면, 최대 가지수가 900C62개라서 완전 탐색으로 해결이 불가능합니다. 저도 처음엔 안될 거 같았지만, 모두 친구 사이인 경우 1가지만 찾는 것이기 때문에 백트래킹으로 완탐으로 가능할 수도 있겠다 생각했습니다. 출력도 오름차순으로 제일 작은 걸 찾으라고 해서 더 믿음을 가질 수 있었는데요, 약간의 믿음이 필요한 문제였던 것 같습니다ㅋㅋ

백트래킹 로직은 크게 어렵지 않았습니다.

한명씩 선택하는 과정에서 기존에 선택한 학생들과 모두 친구 사이인지 확인하고, 그렇지 않다면 바로 다음 탐색으로 넘어가는 방식으로 문제를 해결할 수 있습니다.

// 남아있는 학생들 중 첫번째 인덱스, 선택된 학생 수, 친구 관계인지?, 선택된 학생들
fun pick(start: Int, count: Int, isFriendly: Array<BooleanArray>, pickedStudents: IntArray) {
	
    ...
    
    for (i in start until isFriendly.size) {
        // 선택된 학생들과 친구라면
        if (isValid(i, count, pickedStudents, isFriendly)){
            pickedStudents[count] = i // 학생 선택
            pick(i+1, count+1, isFriendly, pickedStudents) // 재귀 호출
        }
    }

종만북의 소풍 문제와는 달리 모든 학생들과 친구 사이인지 확인해줘야 합니다!

생각 과정

1. 모든 조합을 확인해서 풀 수 있을까? 900C62는 너무 크다. 
2. 탐색 중간중간 가지를 쳐낸다면 가능하지 않을까? 가능한 경우 중 오름차순 하나만 찾는 거니까 더더욱 될 것 같다.
3. 믿음을 갖고 도전한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.system.exitProcess


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (picnicCount, studentCount, infoCount) = readLine().split(" ").map(String::toInt)
    val isFriendly = Array<BooleanArray>(studentCount + 1) {
        BooleanArray(studentCount + 1)
    }
    val pickedStudent = IntArray(picnicCount) // 선택한 학생들을 담을 배열

    repeat(infoCount) {
        val st = StringTokenizer(readLine())
        val s1 = st.nextToken().toInt()
        val s2 = st.nextToken().toInt()

        isFriendly[s1][s2] = true
        isFriendly[s2][s1] = true
    }

    if (picnicCount == 1) { // 1명만 뽑는다면 항상 학생1을 데려갈 수 있다
        print(1)
        return
    }

    pick(0, 0, isFriendly, pickedStudent)

    print(-1)
}

// 남아있는 학생들 중 첫번째 학생, 선택된 학생 수, 친구 관계, 선택된 학생들
fun pick(start: Int, count: Int, isFriendly: Array<BooleanArray>, pickedStudents: IntArray) {
    if (count == pickedStudents.size) {
        pickedStudents.sort()
        printStudents(pickedStudents)
        exitProcess(0)
    }

    // 남아있는 학생 수 < 뽑아야할 학생 수
    if (isFriendly.size - start < pickedStudents.size - count) {
        return
    }

    for (i in start until isFriendly.size) {
        // 선택된 학생들과 친구라면
        if (isValid(i, count, pickedStudents, isFriendly)){
            pickedStudents[count] = i
            pick(i+1, count+1, isFriendly, pickedStudents)
        }

    }
}

fun printStudents(pickedStudents: IntArray) {
    val answer = StringBuilder()

    pickedStudents.forEach {
        answer.append(it).appendLine()
    }
    print(answer)
}

fun isValid(student: Int, end: Int ,pickedStudents: IntArray, isFriendly: Array<BooleanArray>): Boolean {
    for (i in 0 until end) {
        val pickedStudent = pickedStudents[i]
        if (isFriendly[student][pickedStudent].not()) {
            return false
        }
    }

    return true
}

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
}