[Mindev 개발공부]알고리즘 백준 9375번 패션왕 신해빈 Java 풀이

문제는 다음과 같습니다.

예를 들어 다음과 같이 주어진 상황에서 생각해보겠습니다.

hat headgear
sunglasses eyewear
turban headgear

각각 hat,sunglasses,turban 하루하루 한개씩 입는 방법이 3일 존재하며 추가적으로

(hat,sunglasses) 혹은 (sunglasses,turban) 2일 입을수있으며 총 5일동안 밖에 돌아다닐 수 있습니다.

그림을 보시면서 좀더 쉽게 이해 할수있습니다.

각각 종류마다 n1,n2,n3 가지고 있다면 (n1) x (n2) x (n3)

플러스  각각 종류를 입지 않는 경우도 포함 하는 경우의 수 +1 하게되면

 (n1+1) x (n2+1) x (n3+1)

마지막에는 모두 입지 않은 경우의수 -1 를 하게되면 답이 나오게 된다.

전체 코드

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.HashMap;

public class Main {

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

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int a = Integer.parseInt(br.readLine());

for (int i = 0; i < a; i++) {

HashMap<String, Integer> map = new HashMap<>();

int b = Integer.parseInt(br.readLine());

for (int j = 0; j < b; j++) {

String type = br.readLine().split(" ")[1];

if (map.containsKey(type)) {

map.put(type, map.get(type) + 1);

} else {

map.put(type, 1);

}

}

int x = 1;

for (int y : map.values()) {

x *= y + 1;

}

System.out.println(x-1);

}

}

}