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... 이는 당연히 "시간초과 " 가 나게 되네요..  또한 배열의 복사에서 시간을 많이 쓰는 것 같습니다

문제에서 주어진 예제입력은 시간이 걸리긴 하지만 정상적으로 출력이 됩니다  

도저히 이와 같은 풀이밖에 떠오르지 않습니다.. 

어떤 부분을 놓치고 있는지 알려 주시면 감사하겠습니다. 위에서 제가 언급한 부분을 고려를 해주어야 하나요???  

rnjstpgns91   3년 전

판을 만드는 것에서 이미 Rotate가 포함되어있기에 4^5 * 5! 아닌가요?

rnjstpgns91   3년 전

추가적으로 제가 이 코드 그대로 제출해보았는데 통과 됩니다...

고친점은 memset을 이용하기위해 cstring만 include해주었고(제가 쓰는 환경에선 include를 해주어야 memset함수를 사용할 수 있어서)  C++ 14 환경입니다.

axa1239   3년 전

우선 댓글 달아주셔서 너무 감사드립니다!

제 컴퓨터 환경에서는 (vs2017)정답을 출력하기에  4-5초  정도 걸리고 시간제한이 2초이기에 당연히 틀릴줄 알았습니다..  PASS가 나온다니... 작성자님도 비슷한 방법으로 푸신건가요??

rnjstpgns91   3년 전

네 저도 똑같아요 다른점은 DFS + vector로 조합 구현정도인거같네요.

저도 비쥬얼 스튜디오로 돌리는데 이 문제의 경우에 그렇게 시간이 걸리고 디버그모드라서 그럴거예요. 릴리즈모드로 바꿔서 돌리면 바로 답 나오실겁니다.

예전에 본 내용중에 이런 웹에서 제출한 코드는 디버그모드로 검사하는게 아니여서 릴리즈모드 같이 훨씬 빠른속도로 검사한다고 본 기억이 있네요.

axa1239   3년 전

아하..  정답이 조금 느리게 나와도 제출은 해봐야 겠군요 ㅠ
예제를 테스트 하는 환경이 비쥬얼 스튜디오랑은 환경이 다르구나...  디버그 모드 릴리즈 모드.. 덕분에 많이 알아갑니다!!

감사합니다!!!

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