17226번 - 묘수풀이: 모독
먼저, 테스트케이스가 비효율적인 코드를 못 잡습니다.제출번호 22254800 처럼, 2중 for문으로 모든 순열을 시도해보는 경우, 시간 복잡도는 O((n*m)^n)이며, 극단적인 케이스에서는 수백초 이상 걸립니다.
7 71 101 101 101 101 101 101 101 101 101 101 101 101 101 10
하지만, 이 입력의 경우, 출제자의 의도된 정해인, 시간복잡도 O(m^n)에서도 1초 이상의 시간이 걸리는 것으로 보입니다.
6 61 101 101 101 101 101 101 101 101 101 101 101 10
위 입력의 경우에는, O((n*m)^n) 풀이에서는 시간초과, O(m^n)에서는 시간 내로 들어오는 것 같습니다.
또한, 모독을 사용하지 않아도 되는 경우에 모독을 사용하면 오답으로 처리하고 있는 것으로 확인됩니다.
상대 하수인이 모두 죽어있더라도 모독을 사용할 수 없다는 조건이 없기때문에, 지문이 수정되거나 해당 입력 또한 정답으로 간주되어야 할 것입니다.
2 2
2 22 2
위 입력에서,
3attack 1 1
attack 2 2
use modok
의 출력이 나오는 코드는 오답,
2
attack 1 1
의 출력이 나오는 코드는 정답 처리가 되며, 여러 테스트케이스를 통해 확인했습니다.
모독을 사용할 수 있는 조건만 수정하게 될 경우에는,
3attack 1 1use modokattack 2 2
의 출력이 나오는 코드 또한 오답 처리가 될 수 있으므로, '최단 동작으로 상대방의 모든 하수인을 처리할 수 있는' 등의 조건으로 변경되어야 할 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
r4pidstart 4년 전
먼저, 테스트케이스가 비효율적인 코드를 못 잡습니다.
제출번호 22254800 처럼, 2중 for문으로 모든 순열을 시도해보는 경우, 시간 복잡도는 O((n*m)^n)이며, 극단적인 케이스에서는 수백초 이상 걸립니다.
7 7
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
하지만, 이 입력의 경우, 출제자의 의도된 정해인, 시간복잡도 O(m^n)에서도 1초 이상의 시간이 걸리는 것으로 보입니다.
6 6
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
위 입력의 경우에는, O((n*m)^n) 풀이에서는 시간초과, O(m^n)에서는 시간 내로 들어오는 것 같습니다.
또한, 모독을 사용하지 않아도 되는 경우에 모독을 사용하면 오답으로 처리하고 있는 것으로 확인됩니다.
상대 하수인이 모두 죽어있더라도 모독을 사용할 수 없다는 조건이 없기때문에, 지문이 수정되거나 해당 입력 또한 정답으로 간주되어야 할 것입니다.
2 2
2 2
2 2
2 2
2 2
위 입력에서,
3
attack 1 1
attack 2 2
use modok
의 출력이 나오는 코드는 오답,
2
attack 1 1
attack 2 2
의 출력이 나오는 코드는 정답 처리가 되며, 여러 테스트케이스를 통해 확인했습니다.
모독을 사용할 수 있는 조건만 수정하게 될 경우에는,
3
attack 1 1
use modok
attack 2 2
의 출력이 나오는 코드 또한 오답 처리가 될 수 있으므로, '최단 동작으로 상대방의 모든 하수인을 처리할 수 있는' 등의 조건으로 변경되어야 할 것 같습니다.