BOJ 1635

https://www.acmicpc.net/problem/1635

 

코드

http://boj.kr/33d5f3fa46b445aeb0c5ad76a78e0ab1

 

난이도 : P5

 

Elapse Time : 10min

 

처음에는 주어진 $M$개의 수열에 맞춰서 $N$개의 수열을 만들 생각을 해보았지만 수열의 가짓수가 너무 많고 예외 처리를 많이 해주어야 할 것 같아 다른 방법을 생각해 보기로 했다. 우선 조건을 더 강하게 바꿔서 어떤 수열이 주어지든 $N$개 중 하나의 수열을 곱했을 때 수열값이 0이 되게 만들 수 있는지를 생각해 보았다. $N$개가 제한이므로 전체가 1인 수열에서 앞에서부터 $k(0\leq k\leq N-1)$개 까지의 수가 -1인 $N$개의 수열을 준비하면 어떻게 될지 먼저 생각해보았다. 전체 다 1인 수열과 곱했을 때 수열값을 $x$라고 하면 전체가 -1인 수열값은 $-x$가 되는데 $x=0$인 경우에는 전체가 1인 수열이 답이 되고 $x\neq 0$인 경우에는 곱하는 수열 중 원소 하나가 바뀌면 2씩 바뀌기 때문에 $x$에서 $-x$로 수열값이 변하는 과정에서 0을 지나게 될 수밖에 없다는 것을 깨달았고 이를 naive 하게 구현해도 $O(N^2M)$으로 시간 안에 돌아갈 것으로 보여 구현했다.