[Java] 백준(실버-3) 9375번 - 패션왕 신해빈

문제 풀이

---

이번 문제는 조합과 관련된 문제로 HashMap을 이용해 간단히 풀 수 있다.

아이디어 도출

문제의 예시만 잘 살펴봐도 어떻게 풀어야 할지 쉽게 파악할 수 있다. 예시를 보자.

문제의 요구사항을 보면 위에서 두어진 2 종류와 3개의 옷가지를 통해 알몸이 되지 않는 경우의 수를 구해야 한다고 한다.

경우의 수를 바로 구해보자. 이때, 같은 종류의 옷은 입지 못하는 것을 유의하자.

한 개만 입을 경우 : {hat}, {turban}, {sunglasses}
두 개씩 조합하여 입을 경우 : {hat, sunglasses}, {turban, sunglasses}

총 5가지 경우의 수

이렇게 5가지 경우의 수를 구하면 되는데, 조합 공식을 통해 구하는 방법을 알아보자.

[headgear]
hat
turban

[eyewear]
sunglasses

위와 같이 두 종류의 옷마다 1개를 선택하는 경우의 수를 구해야 한다. 그런데 위의 종류의 옷은 저것으로 끝이 아니다! 바로 아무 것도 입지 않는 경우도 포함시켜야 한다.

[headgear]
hat
turban
null

[eyewear]
sunglasses
null

위와 같이 알몸의 아무 것도 입지 않은 경우를 두 종류에 포함시켜서 조합 공식을 적용해야 한다. 그렇게 headgear에서는 3C1을, eyewear에서는 2C1을 구한다.

3C1 = 3
2C1 = 2

이 둘을 곱하면 6으로 모든 종류의 옷을 통해 구한 경우의 수가 된다. 그리고 한 가지 더 유의할 점은 옷의 종류마다 안 입는 경우도 포함시켰기 때문에 모든 경우의 수에는 알몸인 상태가 포함되어 있다. 그래서 (3C1 * 2C1) - 1과 같이 1가지 경우의 수를 차감시켜 알몸인 경우를 제외해야 한다.

이를 통해 문제를 풀기 위해 정리한 아이디어는 다음과 같다.

1. T(테스트케이스)마다 HashMap에 옷의 종류와 옷의 종류의 갯수를 담는다. (이때, 옷 이름은 필요없다.)
2. 같은 옷의 종류가 나온다면 갯수를 1 증가시키고, 같은 종류의 옷이 아니라면 1을 삽입하여 카운트할 수 있도록 한다.
3. HashMap을 순회하며, 옷의 종류마다 알몸의 경우를 고려해(+1) 곱해나가면, 알몸이 아닌 옷의 종류별 모든 경우의 수를 구할 수 있다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());

        while(T --> 0) {
            
            Map<String, Integer> hm = new HashMap<>();
            int N = Integer.parseInt(br.readLine());

            while(N --> 0) {
                String str = br.readLine();
                String cloth_type = str.split(" ")[1];

                /**
                 * 같은 종류의 옷이 hashMap에 존재한다면, 해당 종류의 값을 1씩 증가시킨다.
                 * 같은 종류의 옷이 없다면 값에 1을 삽입한다.
                 */
                if(hm.containsKey(cloth_type)) {
                    hm.put(cloth_type, hm.getOrDefault(cloth_type, 0)+1);
                }else {
                    hm.put(cloth_type, 1);
                }

            }
            
            // 조합을 구할 변수
            int result = 1;

            // 안 입는 경ㅜ를 고해 종류별로 경우의 수ㄹ 1씩 더해야 한다.
            for(int value : hm.values()) {
                result *= (value + 1);
            }
            
            // 모두 안입은 경우의 수 1가지를 감소시킨다.
            result -= 1;

            bw.write(result+"\n");

        }
        
        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.