https://www.acmicpc.net/problem/9375
문제
> 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다.
> 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다.
> 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?접근
map을 통해 옷의 종류를 key값으로 하여 value값으로 옷의 개수를 누적한다. 옷의 이름은 필요없다.
가능한 경우를 구하기 위해 예를들어 안경, 바지 2종류를 조합한다고 하면 안경의 개수 x 바지의 개수 하면 구할 수 있다. 이처럼 1종류, 2종류, 3종류...를 조합할 때의 총 합을 구해주면 된다.
이를 구하려면 종류별 옷의 개수 + 1해준 값을 전부 곱해주면 구할 수 있다. +1해주는 이유는 해당 종류를 입지 않을 경우이다.
이때 알몸은 안된다고 하였으므로 구한 경우에서 전부 안입는 경우를 뽑았을 경우인 1가지를 빼주면 된다.
예제 1은 모자2가지, 안경 1가지이다. 공식을 이용해보면
(2+1) x (1+1) - 1을 하면 된다. 이는 3x2-1로 5가 제대로 나온다.
문제해결
> T로 테스트케이스의 수를 입력받고 반복한다.
> 각 테스트케이스마다 옷의 수 n을 입력받고 n의 범위가 0부터이므로 0일 떄는 따로 0가지라고 예외처리를 해준다.
> 옷의 정보를 저장할 map을 cloth로 입력받는다.
> 이름은 필요없으므로 종류를 key값으로, 종류별 수를 int형 value로 가진다.
> 옷의 수만큼 반복하며 이름은 버리고 다음 token인 종류를 받아 map에 누적한다.
> 각 종류별로 옷의 수인 cloth.values에 +1한 값을 전부 곱해 누적해준다.
> 알몸인 경우 1가지를 빼준 경우의 수 rst를 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//9375번 패션왕 신해빈
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
while(T-->0) {
int n = Integer.parseInt(br.readLine());
if(n == 0) {
sb.append(0).append('\n');
continue;
}
Map<String, Integer> cloth = new HashMap<>();
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
st.nextToken();
String kind = st.nextToken();
cloth.put(kind, cloth.getOrDefault(kind, 0) + 1);
}
int rst = 1;
for(int i : cloth.values()) rst *= (i+1);
sb.append(rst-1).append('\n');
}
System.out.print(sb);
}
}
후기
옷의 종류를 2가지, 3가지...t가지 만 쓸 때를 전부 백트래킹으로 구해주려고 했는데 아무리 생각해도 재귀가 깂어지고, 각 종류별로 재귀가 들어가니 안될것 같았다.
위 경우를 종류별 옷의 수 + 안입는경우1을 해줌으로써 해결할 수 있었다.
