백준 - 사람의 수(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

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

 

[문제 설명]

좀 많이 화가 나는 문제.

 

[접근 방법]

접근은 굉장히 간단하다.

사람이 줄 수 있는 점수는 정수이며 0~10점 사이.

소수점 3자리까지 나와야하므로 최악의 경우에도 사람은 1000명을 넘지 않는다.

왜냐? 3자리인 소수는 무조건 분모가 1000인 분수로 표현 가능하니까.

예 : 0.123 == 123/1000, 1.456 == 1456/1000, 0.334 == 334/1000

 

그렇다면, 사람 1명인 경우부터 1000명인 경우까지 모든 경우를 따져보면 된다.

점수의 총합이 될 수 있는 값으로는 0점 ~ 10*인원수가 된다.

 - 예시 - 

사람 1명 => 총합의 최저값은 0점, 최댓값은 10점.

사람 5명 => 총합의 최저값은 0점, 최댓값은 50점.

 

여기까지 보면, 그냥 완전탐색으로 보이지만 여기서 이분탐색을 사용하여 시간을 줄일 수 있다.

사람은 1명부터 1000명까지 전부 검색해야 하지만, 점수는 타겟인 값보다 크냐 작냐에 따라 이분 탐색이 가능하다.

예를 들어, 현재 사람이 8명이고, 타겟은 0.75가 되야 한다고 하자.

1/8, 2/8, 3/8, .. 5/8, 6/8 이런 식으로 선형 탐색을 하는 방법도 있다.

하지만, 이분 탐색을 이용하면 시간을 굉장히 줄일 수 있다.

먼저 가운데부터 체크한다. 4/8은 타겟보다 작으므로 하한선을 가운데로 옮겨 준다.

5~8에 중간인 6을 이용해서 타겟과 같은지 체크한다. 6/8은 0.75와 같으므로 정답이다.

 

여기까지 아이디어는 생각보다 간단했지만, 소수점 오차 때문에 시간을 많이 잡아먹었다.

결국엔, 1000을 곱하여, 모든 값을 정수로 처리해서 풀었다. 

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

private lateinit var averages: IntArray
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    averages = IntArray(n)
    repeat(n) {
        val input = br.readLine().split(".")
        val sb = StringBuilder()
        sb.append(input[0]).append(input[1])
        averages[it] = sb.toString().toInt()
    }

    for (cntOfPeople in 1..1000) {
        // 현재 인원수가 분모일 때, 모두 일치하는지 확인
        if (isPossibleCnt(cntOfPeople = cntOfPeople, averages = averages)) {
            println(cntOfPeople)
            break
        }
    }
}

fun isPossibleCnt(cntOfPeople: Int, averages: IntArray): Boolean {
    for (avg in averages) {
        var left = 0
        var right = 10 * cntOfPeople
        var isPossible = false
        while (left <= right) {
            // 총 점수
            val sumOfScore = (left + right) / 2
            val currentAvg = (sumOfScore * 1000) / cntOfPeople

            // if : 평균값이 타겟과 같으면
            if (currentAvg == avg) {
                if (currentAvg > 10 * 1000) {
                    continue
                }
                isPossible = true
                break
            } else if (currentAvg > avg) {
                right = (sumOfScore - 1)
            } else {
                left = (sumOfScore + 1)
            }
        }

        if (!isPossible) {
            return false
        }
    }
    return true
}

 

[반성]

이런 문제가 있을 때마다 날먹처럼, float면 double로 바꾸고 이것 저것 대충대충 넘어갔는데 이번에 제대로 혼났다.

내일은 오랜만에 부동소수점 오차를 복습해야겠다...