[백준-자바] N_9375 패션왕 신해빈

0woy·2024년 10월 29일
0

코딩테스트

목록 보기
32/40

📜 문제

  • 해빈이가 옷 하나만 걸쳐도 되니까 나체만 아닌 모든 경우의 수
  • 종류별로 한 개만 입을 수 있음 ex) 모자 두 개 안 됨

생각하기

내가 제일 약한 분류인 조합 문제이다.
그런데 걸치는 옷의 조합을 나열하는 게 아닌 단지 경우의 수만 구하는 거라서 수학으로 풀 수 있지 않을까 싶었다. (재귀 짜다가 번뜩 생각남)
하지만, 기껏 짜놓은 재귀가 아깝기도 했고.. 시간도 많이 지나서 그냥 제출하고 25%에서 실패해서 답 봤다.

풀이 방법은 결국 수학이지롱

접근 방식

headgear - hat, turban
eyewear - sunglasses

위와 같이 예제가 주어졌지만, 문제에서는 해빈이가 나체만 아니면 된다고 했다.
즉, 우리는 아래와 같이 아무것도 안 입는 선택지도 분류에 넣어주고 경우의 수를 구해야 한다.

headgear - hat, turban,NONE
eyewear - sunglasses, NONE

그러면, 우리가 구할 수 있는 경우의 수는
headgear 종류에서 1개 * eyewear 종류에서 1개
= ₃C₁X ₂C₁ = 3 X 2 = 6

이때, 두 종류 모두 NONE을 고르는 경우가 포함돼 있으므로 결과값에서 1을 빼주면 답이 된다.


🍳 전체 소스 코드

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

public 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 tc = Integer.parseInt(br.readLine());

        while(tc-- >0){
            Map<String, Integer> map = new HashMap<>();
            int count  = Integer.parseInt(br.readLine());
            while(count -- >0){
                StringTokenizer st = new StringTokenizer(br.readLine());
                st.nextToken();
                String sort = st.nextToken();
                map.put(sort, map.getOrDefault(sort,1)+1);
            }
            long result = 1;
            for(String key: map.keySet()){
                result*=map.get(key);
            }
            result-=1;
            bw.write(result+"\n");
        }
        bw.flush();
        bw.close();
    }
}

✍ 부분 코드 설명

입력

public 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 tc = Integer.parseInt(br.readLine());

        while(tc-- >0){
            Map<String, Integer> map = new HashMap<>();
            int count  = Integer.parseInt(br.readLine());
             while(count -- >0){
                StringTokenizer st = new StringTokenizer(br.readLine());
                st.nextToken();
                String sort = st.nextToken();
                map.put(sort, map.getOrDefault(sort,1)+1);
            }
        ...
  • Map: key에는 옷의 종류, value에는 해당 종류의 옷 개수를 넣어준다.

경우의 수 구하기

     long result = 1;
            for(String key: map.keySet()){
                result*=map.get(key);
            }
            result-=1;
            bw.write(result+"\n");
        }
        bw.flush();
        bw.close();
    }
}
  • map을 순회 하면서 구한 경우의 수를 result 변수에 삽입한다.
  • 나체인 경우의 수가 포함돼 있으니 result에서 1을 제한다.

✨ 결과

조합만 나오면 벌벌 떤다.
이번 문제는 나열하는 게 아니기 때문에 수학적으로 접근하여 푸는 거였지만
나열하라는 문제가 나오는 걸 대비해서 외우든가 알아도야겠다.


📖 참고

Stranger's LAB - [백준] 9375번 : 패션왕 신해빈

0개의 댓글