[JAVA] 백준 9375번: 패션왕 신해빈

 

---

문제

• 주어지는 옷들을 조합해 입고 다니되, 같은 옷의 조합을 입으면 안된다는 조건이 붙을 때, 옷을 조합해 입고다닐 수 있는 날의 최댓값을 구하는 문제.

 

아이디어

• 선글라스 3개, 바지 2벌의 경우를 생각해보자
  • 선글라스만 골랐을 때, 각 종류의 선글라스 3개를 각각 고르는 경우 3가지 + 선글라스를 고르지 않는 경우 1가지, 총 4가지의 경우의 수가 나온다.
  • 바지만 골랐을 때, 각 종류의 바지 2벌을 각각 고르는 경우 2가지 + 바지를 고르지 않는 경우 1가지, 총 3가지의 경우의 수가 나온다.
  • 따라서, 선글라스와 바지를 조합하는 경우는 4 x 3, 여기에 둘 다 고르지 않는 경우는 존재하지 않아야 하므로 - 1가지를 해 총 11가지의 경우의 수가 존재하게 된다.
• 즉, "각 타입의 종류 수 + 1" 한 값을 각각 모두 곱해준 후, 1을 빼주면 옷의 조합을 입고다닐 수 있는 최댓값이 나오게 된다.
• 같은 타입의 옷을 카운트 해야 하므로, 해시 맵을 선언해 저장하고, 기존에 있는 값이면 getOrDefault를 사용해 갱신한다.

 

풀이

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        Map<String, Integer> map;

        int T = Integer.parseInt(br.readLine());
        for(int t=0; t<T; t++) {
            map = new HashMap<>();
            int N = Integer.parseInt(br.readLine());
            
            // map에 옷 카운트
            for(int n=0; n<N; n++) {
                st = new StringTokenizer(br.readLine());
                st.nextToken();
                String type = st.nextToken();
                map.put(type, map.getOrDefault(type, 0)+1);
            }
            
            // (각 제품의 종류 + 1) 값을 누적해서 곱함
            int answer = 1;
            for(int v: map.values()) {
                answer *= (v+1);
            }
            sb.append(answer-1).append('\n');
        }
        System.out.println(sb);
    }
}

 

 

채점 결과

9375번 채점 결과

 

문제 링크

• 9375번: 패션왕 신해빈 (acmicpc.net)