백준 - 패션왕 신해빈(Kotlin)

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

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

 

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

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

문의는 댓글 바람.

 

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

 

[문제 설명]

해빈이가 옷을 입을 수 있는 경우

 

[접근 방법]

처음 접근할 때는 문제 그대로 입을 수 있는 경우를 구하는 방법을 생각했다.

예를 들어, 상의가 2개고 하의가 1개라면

=> 상의 1개만 입는 경우 + 하의 1개만 입는 경우 + (상의 1개만 입는 경우 * 하의 1개만 입는 경우) => 2 + 1 + (2  * 1) = 5

그러나, 위같은 경우에는 시간이 굉~~장히 많이 걸리게 된다.

옷의 종류 개수가 s라고 할 때, 옷을 1개 고르는 경우 2개 고르는 경우 .. s개 고르는 경우를 구해야 하는데.

이는 시간복잡도가 2^s이 된다.

주어진 옷의 개수에 최댓값은 30이고, 따라서 옷의 종류의 최댓값은 30이 된다.

즉, 여기까지만 해도 시간복잡도가 2^30이 된다는 거다.

거기다 테스트는 최대 100개. 최악의 경우 100 * 2 ^ 30

즉, 시간복잡도는 O(t * 2 ^ n)이 된다. 절대 통과할 수 없다.

 

방법 2는 반대로 생각하는 거다.

전체 경우의 수 = 알몸인 경우 + 알몸이 아닌 경우이다.

따라서, 알몸이 아닌 경우 = 전체 - 알몸인 경우.

전체는 종류별 옷의 개수 + 1을 모두 곱한 값이다.

예 : 

모자 머리

볼캡 머리

안경 눈

위와 같은 경우, 모자를 쓴 경우와 볼캡을 쓴 경우 그리고 쓰지 않은 경우(2 + 1).

눈은 안경을 쓴 경우와 안경을 쓰지 않은 경우(1 + 1).

즉, 3 * 2가 전체 경우의 수가 된다.

여기서 1(알몸인 경우)을 빼면 알몸이 아닌 경우가 된다.

 

[내 답안]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.StringTokenizer

fun main() {
    // 해빈이는 입었던 옷들은 다시 입지 않는다.
    // ex : 안경, 코트, 상의, 신발을 입었다면 다음날엔 바지를 추가로 입거나 || 안경 대신 렌즈를 착용해야 합니다.
    // 가진 의상들이 주어졌을 때 며칠동안 알몸이 아닌 상태로 돌아다닐 수 있을까.
    // 1 <= t(테스트 케이스 개수) <= 100
    // 0 <= n(옷 개수) <= 30

    // 방법 1
    // 입을 수 있는 부위 개수(cntOfWearPart)가 있으면 여기서 1개 고르기, 2개 고르기, 3개 고르기, ... , 입을 수 있는 부위 개수 다 고르기
    // 예 :
    // 머리 : 2
    // 눈 : 1
    // 머리 중에 1개 고르기(2) + 눈 중에 1개 고르기(1) + (머리 중에 1개 고르기(2) * 눈 중에 1개 고르기(1)) = 5
    // 즉, 몸에서 1개 고른 경우, 몸에서 2개 고른 경우, 몸에서 3개 고른 경우, .. , 몸에서 cntOfWearPart개 고른 경우.
    // 이 경우에 시간 복잡도는? O(t * n ^ n) => t * n ^ n = 100 * 2 ^ 30 => 너무 크다.

    // 방법 2
    // 전체 = 옷을 하나라도 입은 날 + 알몸인 날
    // 전체 - 알몸인 날 = 옷을 입은 날
    // 전체 = 옷들로 만들 수 있는 모든 조합 => 각 옷의 개수 + 1을 모두 곱한 값. + 1을 해주는 이유는 벗은 경우도 생각해서.
    // 옷을 입은 날 = (머리 옷의 개수 + 1) * (상의 옷의 개수 + 1) * ... * (신발 옷의 개수 + 1) - 1(알몸)
    val cntOfTest = readln().toInt()
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val br = BufferedReader(InputStreamReader(System.`in`))
    repeat(cntOfTest) {
        val cntOfClothes = br.readLine().toInt()
        val map = mutableMapOf<String, Int>()
        repeat(cntOfClothes) {
            val st = StringTokenizer(br.readLine())
            st.nextToken()
            val part = st.nextToken()
            map[part] = map.getOrDefault(part, 0) + 1
        }
        bw.write("${getUnNakedDay(map)}\n")
    }
    bw.flush()
}

fun getUnNakedDay(map: MutableMap<String, Int>): Int {
    var unNakedDay = 1
    map.values.forEach {
        unNakedDay *= (it + 1)
    }

    return unNakedDay - 1
}