bluefire   2년 전

안녕하세요 '초차원전쟁 이나'에 대해서 질문이 있어서 왔어요


만약 처음 1이 되는 xi의 위치가 각 n단위 이동에 대해서 유일하다면 이 문제는 쉽게 해결이 될 것 같은데


만약 단 하나라도 xi가 같은 경우에는 경우의 수가 너무 커지게 되고, 이걸 수식으로서 단순화 하기도 힘들어보이네요


도무지 문제를 해결할 방법이 보이지 않네요.


문제를 더 단순화 해서 x1 x2 x3 ... xn인 정수가  주어졌을때 음이 아닌 정수를 곱해서 k를 만들 수 있나 없나


정도는 판별은 가능할 것 같은데, n차원에 대해서는 굉장히 어렵네요.


혹시 이 문제에 대해서 힌트를 주실수 있나요??


jh05013   11달 전

1년이나 된 질문이지만, 문제에 심각한 오류가 있어서 댓글을 남깁니다.

처음 나오는 1의 위치는 서로 다르며, 증가하는 순서대로 입력이 주어집니다. 서로 다르다는 조건이 빠지면 NP-하드 문제임을 증명할 수 있습니다.

https://www.acmicpc.net/board/...

댓글을 작성하려면 로그인해야 합니다.