2
4 6
cl bom dara minzy
2 dara minzy
2 cl minzy
2 cl dara
1 cl
2 bom dara
2 bom minzy
10 7
a b c d e f g h i j
6 a c d h i j
3 a d i
7 a c f g h i j
3 b d g
5 b c f h i
4 b e g j
5 b c g h i
를 입력했을 경우
첫 번째 경우는 계산되는 수가 23
두 번째 경우는 계산되는 수가 45 로
2^6과 2^7에 비해 계산해야되는 수를 1/3 정도로 줄였는데도 시간초과가 나네요.. ㅜㅜ 풀려면 얼마나 더 줄여야 되는건가요??
우선 예제만 가지고 큰 데이터에 대해 경우의 수가 줄어드는 비율을 이야기하는 것은 어렵습니다. 어떻게 구현하셨는지는 모르겠지만, 실제로 큰 데이터의 경우 1/3보다 더 줄어들기는 할 것입니다. 그러나, 경우의 수를 1/100으로 줄인다 하더라도 250의 1/100은 어마어마하게 큰 수인 것 역시 생각하셔야 합니다.
int_solution
보기에 나온 예제대로 하면
2
4 6
cl bom dara minzy
2 dara minzy
2 cl minzy
2 cl dara
1 cl
2 bom dara
2 bom minzy
10 7
a b c d e f g h i j
6 a c d h i j
3 a d i
7 a c f g h i j
3 b d g
5 b c f h i
4 b e g j
5 b c g h i
를 입력했을 경우
첫 번째 경우는 계산되는 수가 23
두 번째 경우는 계산되는 수가 45 로
2^6과 2^7에 비해 계산해야되는 수를 1/3 정도로 줄였는데도 시간초과가 나네요.. ㅜㅜ 풀려면 얼마나 더 줄여야 되는건가요??
10년 전