판을 만드는 것에서 이미 Rotate가 포함되어있기에 4^5 * 5! 아닌가요?
16985번 - Maaaaaaaaaze
판을 만드는 것에서 이미 Rotate가 포함되어있기에 4^5 * 5! 아닌가요?
추가적으로 제가 이 코드 그대로 제출해보았는데 통과 됩니다...
고친점은 memset을 이용하기위해 cstring만 include해주었고(제가 쓰는 환경에선 include를 해주어야 memset함수를 사용할 수 있어서) C++ 14 환경입니다.
네 저도 똑같아요 다른점은 DFS + vector로 조합 구현정도인거같네요.
저도 비쥬얼 스튜디오로 돌리는데 이 문제의 경우에 그렇게 시간이 걸리고 디버그모드라서 그럴거예요. 릴리즈모드로 바꿔서 돌리면 바로 답 나오실겁니다.
예전에 본 내용중에 이런 웹에서 제출한 코드는 디버그모드로 검사하는게 아니여서 릴리즈모드 같이 훨씬 빠른속도로 검사한다고 본 기억이 있네요.
댓글을 작성하려면 로그인해야 합니다.
axa1239 3년 전
안녕하세요 읽어 주셔서 감사합니다!
저의 문제풀이는 다음과 같습니다.
1. 5개의 판을 몇층에다가 쌓을지 정해 줍니다 이는 5! 존재 하므로 next_permutation 을 이용해서 구현해 주었습니다.
- > 하지만 1번판 2번판 ... 5번판이라고 한다면 각각을 1층 2층 3층 .. 5층에 넣어 본다고 생각을 해본다면 이는 1-2-3-4-5 와 5-4-3-2-1 은 같은 경우이므
로 최적화가 가능 할 것 같지만 이는 고려해 주지 않았습니다.
회전연산의 경우 (5^2)
2. 각각의 판들의 위치를 정해 주었으니 원판 혹은 회전시킨것 총 4개의 판이 생길 수 있습니다. 1번을 정해준 경우의 4 ^ 5 의 경우의 수가 존재하게 되구요
3. 최종적으로 판들이 위치 및 정확한 모양이 정해 졌으니 입구에서부터 출구 까지 bfs를 통해서 갈 수 있는지 조사를 합니다 (5^2)
5! * (4 ^5 ) * 회전연산 (5^2) * bfs(5^3) = > 3억 XX... 이는 당연히 "시간초과 " 가 나게 되네요.. 또한 배열의 복사에서 시간을 많이 쓰는 것 같습니다
문제에서 주어진 예제입력은 시간이 걸리긴 하지만 정상적으로 출력이 됩니다
도저히 이와 같은 풀이밖에 떠오르지 않습니다..
어떤 부분을 놓치고 있는지 알려 주시면 감사하겠습니다. 위에서 제가 언급한 부분을 고려를 해주어야 하나요???