5개의 댓글이 있습니다.
-
-
winner -
같이 고민해주셔서 감사합니다..
Wooden Stick 문제는 최근 후배들이 풀어볼려고 해서 한번 여기에 올려봤습니다. 사실 이 문제는 3년 전 쯤 친구가 회사입사 실기시험으로 Java coding을 보는데 도와달라고 해서 같이 풀어보자고 했었던 문제였습니다. 친구가 이게 어떻게 정답인지 말할 수 있냐고 해서 이런 저런 고민을 했는데 Hasse Diagram을 그려보니 대충 이게 답이다는 느낌은 들었지만 명확히 증명과정이 나오지 않아서 설명은 결국 못해줬던 기억이 있습니다. 재미있었던 것은 Hasse Diagram을 그려보니 예전에 풀다 실패했던 문제 2002년 Dhaka A번 Air Raid 와 동일한 문제라는 것을 알았습니다. Air Riad 문제 풀려고 밤새서 고민했었는데 이미 예전에 풀었던 문제랑 동일했었었죠. 사실 Wooden Stick 문제도 선배가 알려줬었기 때문에 푸는 방법은 알았었지만(당시에는 Hasse Diagram이 뭔지도 몰랐습니다. -_-.) 증명을 안 해 봤었는지 귀찮았는지 증명해줄 수 있냐고 물어보니 안 해주더군요... -_-.
15년 전 link
-
-
-
JongMan -
아 이거 글이 올라왔을 때 고민을 좀 해봤었는데, 의외로 쉽지 않더군요. ^^;; 대회 당시에도 증명해서 푼 팀이 많진 않았을 거란 생각이 드네요. (다섯 팀밖에 못 풀었지만... -.-) 대회 때는 실제로 증명을 안 하고 서브밋을 하는 경우도 꽤 있습니다. 코딩이 간편해서 금방 짤 수 있는 경우에만요. :) 하지만 증명이 될 것 같다/아닐것 같다 라는 직관을 얻기 위해서는 실제로 연습 때 직관을 많이 해 봐야겠지요. ^^;
Safe 문제는.. 당시 해법이 어땠는지 모르겠지만 저라면 O(2^N * N) 동적 계획법으로 풀겠습니다. 각 위치에 있는 손잡이를 두 번 돌릴 필요가 없다는 것은 당연하지요. 두 번 돌리면 안 돌린 거랑 똑같으니까.. 그러면 모든 핸들은 최대 한 번만 돌린단 얘기가 됩니다. 이 때, 핸들들을 돌리는 순서가 중요하지 않다는 것 또한 명백하지요. 따라서, 맨 윗줄 맨 왼쪽에서부터 돌린다고 가정합시다. 그러면 해당 시간 복잡도의 동적 계획법을 얻을 수 있습니다.... 라고 쓰고 혹시해서 게시판을 봤는데 초간단 해법이 있군요.
.... 좀더 생각 후 다시 리플 달아드리죠. -_-
15년 전 link
-
-
-
winner -
약간 이상한데요. 다섯 팀이 풀었다고 했는데 Wooden Stick에 대한 기록을 보면 11팀이 풀었습니다. 2006년
금고문제는 6팀이 풀었고요. 그리고 금고문제의 동적계획법은 이해가 안되네요. 우선 O(2^N * N) 이라고 쓰셨는데 여기서
N이 문제에 주어진 사각형의 한 변의 크기 N을 말하나요? 순서가 중요하지 않다는 말은 맞는데 그렇다고 그것이 동적계획법인지는 모르겠습니다. O(2 ^ (N*N))을 말씀하시는 것이 아닌가 싶은데요. 제가 착각하는 것이 아니라면 설명해주시면 감사하겠습니다.
2006년 대회에는 제가 참가했었는데 제가 그 문제를 맡았었고, 아마도 JM님이 말씀하신 방법으로 풀었던 것으로 기억합니다. 저는 backtracking이라고 생각을 했었습니다만... 당시 에라, 모르겠다. 하다보면 뭔가 경우의 수가 줄어드는 형태가 아닐까 하고 착각해서 시도했다가 대회끝날 즈음 test case에 대한 답을 내는 실행소요시간에 좌절했었죠. 그리고 거짓말장이 찾기 문제 같은 backtracking 도중 경우의 수가 줄어드는 형태가 아님을 이해하고 자신감이 들지 않으면 시도하지 말자고 마음먹었던 기억이 납니다.
15년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
winner
http://acm.kaist.ac.kr/2001/problem.html
B번 문제인데 저는 정렬을 한 후에 pass 수를 세서 문제를 풀었습니다.
다만 그 기법을 명확하게 설명하기 위한 증명은 실패했었습니다.
설명해주시면 감사하겠습니다.
Hasse Diagram을 그려놓고 이리저리 생각하다가 결국 포기했는데요.
관련 문헌을 소개해주셔도 감사하겠습니다.
또 하나 궁금한 것 http://acm.kaist.ac.kr/2006/contest_0923/F_Safe.pdf 인데
푸는 방법은 당시 게시판에서 알긴 했는데 증명을 못하겠더군요.
역시 도와주신다면 감솨!!
15년 전