옷의 종류와 종류에 따라 옷들이 주어진다. 이때 주어진 옷 종류 별로 옷을 고를 때의 경우의 수를 모두 구하는 문제이다. 옷의 종류는 얼굴, 상의, 하의, 겉옷으로 무조건 한 개 이상은 입어야 한다. 종류 중에 하나 상의만 입는 것도 경우의 수에 포함된다.
문제 링크 : 위장
처음 의상의 수가 최대 30개라서 bruto force로 풀 수 있을 거라 생각하지만 30개에서 의상의 종류가 다양하게 나눠지고 거기서 또 옷을 입거나 안입는 경우의 수까지 고려해야하기 때문에 경우의 수가 엄청 커지고 구현하기 복잡해진다. 따라서 수학적으로 경우의 수를 계산하는 방법이 필요하다.
만약 상의 : 2, 하의 : 1 일 때
상의와 하의 둘 중에 하나를 안입는 경우의 수를 구해야 하기 때문에 각 의상 종류에 안입는 경우의 수를 생각해서 1 더해준 뒤 모든 종류를 곱해주면 된다.(아무것도 안입는 경우는 빼줘야 한다)
1. 상의1 + (안입는다)
2. 상의2 + (안입는다)
3. 하의1 + (안입는다)
4. 상의1 + 하의1
5. 상의2 + 하의1
6. (안입는다) + (안입는다) <-- 아무것도 안입는 경우는 제외
따라서 (상의 2 + 1) * (하의 1 + 1) - 1(안입는 경우) 라는 식이 나온다.
import java.util.*;
class Solution {
public int solution(String[][] clothes) {
int answer = 0;
HashMap<String, Integer> map = new HashMap<>();
for (int i=0;i<clothes.length;i++) {
int idx = 1;
if (map.containsKey(clothes[i][1])) {
idx = map.get(clothes[i][1]) + 1;
}
map.put(clothes[i][1], idx);
}
answer = 1;
for (String str : map.keySet()) {
answer *= map.get(str) + 1;
}
return answer - 1;
}
}