백준 1581 락스타 락동호 Kotlin (많은 조건 분기)

문제 출처 : https://www.acmicpc.net/problem/1581

1581번: 락스타 락동호

문제

한국이 낳은 세계적인 락스타 락동호는 2007년 2월 1일 역대 최대 규모의 콘서트를 열었으며, 2007년 2월 11일에 자신의 음악세계를 세상에 알리고, 2007년 3월 4일에는 자신의 작곡 비법을 세계에 공개했다. 하지만, 그 후 락동호는 음악을 접고 체스에 입문하게 되었고, 그 결과 2007년 3월 31일 Heroes원정대에서는 체스 부분으로 참가하게 된다. 그 후 절대로 음악을 하지 않을 것 같았지만, 모두의 예상을 깨고, 2007년 4월 21일 월드 노래자랑으로 신이 내린 가창력으로 우승한 뒤 자취를 감추었다.

하지만 2008년 7월 13일 드디어 락동호가 컴백한다.

락동호는 지난 몇 달간 자신의 신보에 자신의 음악적 능력을 모두 담았고, 이제 몇몇 곡 중 최고의 곡만을 앨범에 담으려고 한다.

락동호는 빠르게 시작해서 빠르게 끝나는 노래를 FF개 만들었고, 빠르게 시작해서 느리게 끝나는 노래를 FS개, 느리게 시작해서 빠르게 끝나는 노래를 SF개, 그리고 느리게 시작해서 느리게 끝나는 노래를 SS개 만들었다.

락동호는 위와 같은 노래 중 총 몇 개를 자신의 새로운 앨범에 넣어야 할지 결정해야 한다. 그리고 당연히 모든 노래는 두 번 이상 앨범에 등장할 수는 없다.

하지만, 락동호는 이제 세계적인 락스타가 아니다. 따라서, 음반사의 엄청난 제한을 지켜서 앨범에 곡을 수록해야 한다. 이번 앨범으로 다시 자신의 지위를 되찾으려고 하는 락동호이기 때문에, 어쩔 수 없이 이 제한을 지키기로 했다.

1. 빠르게 시작하는 노래는 반드시 빠르게 끝나는 노래의 바로 다음에 와야 한다.
2. 느리게 시작하는 노래는 반드시 느리게 끝나는 노래의 바로 다음에 와야 한다.
3. 동호가 녹음한 노래 중 빠르게 시작하는 노래가 한 개라도 있다면, 앨범의 가장 첫 곡은 빠르게 시작하는 곡이어야 한다. 만약, 빠르게 시작하는 노래가 하나도 없다면, 이 제한은 무시해도 된다.

동호는 음반사가 제한한 제한을 지킬 것이다. 하지만, 자신의 수많은 팬들에게 자신이 아직 건재하다는 것을 알리기 위해 음반에 최대한 많은 곡을 넣으려고 한다.

FF, FS, SF, SS가 주어졌을 때, 동호가 음반사의 제한을 어기지 않고, 최대 몇 곡을 실을 수 있는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 FF FS SF SS가 순서대로 들어온다. 모든 수는 0보다 크거나 같고, 1,000보다 작거나 같은 정수이고, 적어도 하나의 수는 0보다 크다.

출력

첫째 줄에 정답을 출력한다.

알고리즘 분류

• 많은 조건 분기

풀이

많은 조건 분기라기에 내가 푼 풀이는 그냥 구현 느낌이다.

크게 f로 시작하는 경우, s로 시작하는 경우로 나눴는데 더 최적화할 수 있을 것 같다.

많은 조건 분기로 풀면 깔끔한 코드가 나올 것 같지만 뇌를 비우고 풀자.

 

풀이는 다음과 같다.

우선 ff 혹은 fs가 1개라도 있는 경우 무조건 f로 시작해야 한다.

ff와 ss를 생각하면 이 친구들은 다른 친구와 상관없이 혼자서 계속 들어갈 수 있다.

따라서 현재 마지막이 f면 ff를 바로 모두 사용할 수 있기 때문에 ff의 개수를 모두 더해주고,

s도 마찬가지로 ss를 바로 모두 사용할 수 있기 때문에 ss의 개수를 모두 더해준다.

시나리오를 생각해 보자.

f로 시작한 경우 ff는 모두 사용했다. 이제 fs, ss, sf를 사용해야 하는데 fs가 하나라도 있다면 s영역으로 넘어갈 수 있다.

따라서 fs가 하나 이상이라면 answer에 1을 더해주고(fs 한 개 사용) s로 넘어간다.

s로 넘어간다면?! ss는 모두 사용할 수 있기 때문에 ss의 모든 개수를 answer에 더해준다.

이제 남은건 sf와 fs이다.

fs는 f에서 s로 넘어갈 때 하나 사용했기 때문에

fs-1, sf개가 남아있을 것이다.

이 둘은 서로 상호보완이다.

sf를 사용하려면 fs가 있어야 하고, fs를 사용하려면 sf가 있어야 한다.

sf가 50이고 fs가 70이라면 sf 50개, fs50개만 사용할 수 있는 것이다.

이렇게 사용 가능한 sf와 fs를 모두 썼다고 하면 

sf는 0개, fs는 20개가 남아있다.

 

여기서 주의할 점!

우리는 처음에 f에서 s로 넘어갔고 마지막으로 s에서 시작해서 sf, fs를 반복했다.

그럼 최종적으로 sf로 시작했기 때문에 사용 가능한 sf 50개, fs 50개를 다 썼더라도 sf가 하나 이상 남아있다면 1을 더해줄 수 있는 것이다.

 

sStart도 위와 같은 흐름으로 풀면 된다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
var answer = 0
var ff = 0
var fs = 0
var sf = 0
var ss = 0

fun fStart() {
    answer += ff
    if (fs > 0) {
        answer++
        fs--
        answer += ss
        val min = fs.coerceAtMost(sf)
        answer += min * 2
        fs -= min
        sf -= min
        if (sf > 0) answer++
    }
}

fun sStart() {
    answer += ss
    if (sf > 0) {
        answer++
        sf--
        answer += ff

        val min = fs.coerceAtMost(sf)
        answer += min * 2
        fs -= min
        sf -= min
        if (fs > 0) answer++
    }
}

fun main() = with(System.out.bufferedWriter()) {
    getIntList().also{
        ff = it[0]
        fs = it[1]
        sf = it[2]
        ss = it[3]
    }
    if (ff > 0 || fs > 0) {
        fStart()
    } else {
        sStart()
    }
    write("$answer")
    close()
}