[백준 / BOJ] 9375 패션왕 신해빈 (Java)

문제

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

9375번: 패션왕 신해빈

해빈이는 N개의 옷을 갖고있다. 

패션에 매우 민감한 해빈이는 날마다 다른조합의 옷을 입어야한다. 이때, 해빈이가 옷을 조합이 겹치지않게 입을수있는 최대 날짜를 계산하는 문제다.

 

---

풀이

솔브드 난이도가 실4로 되어있길래, 생각없이 백트래킹으로 풀었는데, 시간초과가 났다. 

N이 최대 30이므로 모든 조합을 구해서 더해주는 방식으로 계산할경우, O(N!)시간복잡도가 나와서 시간초과가 난다.

 

수학적으로 접근해서 풀은문제다.

 

로직은 간단한데, 해빈이가 "옷을 하나도 입지않은 경우"까지 포함해서 계산하면된다.

모든 상태에 입지않은 상태를 추가한후에, 옷을입지않은경우 까지 계산한후, -1을 해주면 답이된다.

 

주요 소스코드

    private long calc(int[] arr, int size){
        long ret = 1;
        for(int i = 0; i < size; i++) ret *= arr[i];
        return ret-1;
    }

이때, arr[idx]에 종류별 의상의 갯수가 저장되어있다.

(초기에 백트래킹으로 풀었기때문에, 계산이 용이하게, HashMap을 Array로 변환해주는 중간계층함수가 있음)

    private int[] mapToArray(HashMap<String, Integer> hm){
        int[] arr = new int[hm.size()];
        int idx = 0;
        for(String key : hm.keySet()) {
            arr[idx] = hm.get(key)+1;
            idx++;
        }
        return arr;
    }

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/9375%20%ED%8C%A8%EC%85%98%EC%99%95%20%EC%8B%A0%ED%95%B4%EB%B9%88/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃