mosw7   1년 전

돌 게임 8번 문제에서 막히네요.


다른 돌 게임 문제들처럼 순환 주기를 구하는게 포인트인거 같은데

가져갈 수 있는 동전의 개수 a1 ~ ak가 주어졌을 때

O(1)으로 cycle을 구하는 방법이 있으려나요?


일단 무식하게 동전 개수에 대한 승패를 bool 배열로 쭉 만들고

길이 n인 사이클이 있는지 하나하나 체크하는 식으로 풀었는데

(b[1] ~ b[n]과 b[n+1] ~ b[2n]을 비교하는 방식)


1) 부분수열이 있는 경우 잘못 체크 (ex. 00100110010011에서 0010011이 아니라 001을 고름)

2) 순환이 뒤에서부터 나타나는 경우 체크 불가능 (ex. 000001010101에서 01을 찾아내지 못함)

의 문제가 발생하더라고요.


그리고 대부분의 경우 cycle이 ai + aj 꼴로 나타나지던데 (kC2개만 체크하면 되는줄 알았는데)

또 몇몇 경우에서는 그렇지 않았고요. (ex. k = 3일 때, 1, 4, 5 를 입력할 경우 cycle이 8)


그래서 질문은

1) 위 방식대로 수열의 cycle을 구해서 푸는게 맞나요? (그렇지 않다면 a1 ~ ak에 대한 O(1) 풀이가 존재하나요?)

2) 만약 그렇다면, 위 문제점들을 해결할 힌트 좀 주실 수 있나요?


감사합니다.

yukariko   1년 전

저는 cycle을 구해서 문제를 해결했습니다.

다만 cycle의 길이가 몇일지를 확정짓지 못해서 최대 cycle 크기를 가정했습니다. 대략 550 까지로 잡으면 정답이 뜨더군요.

길이 구하는 공식을 모르니 O(1) 일지는 모르겠네요 ㅎㅎ

mosw7   1년 전

네 감사합니다!

지금 아이디어를 그대로 가져가면서 문제들을 보완해야겠네요.

cycle이 550 이하면 TL이 뜨지는 않겠군요 ㅎㅎ

며칠동안 고민하다가 드디어 풀렸네요 ㅜㅜ

저도 사이클 구해서 풀었는데, 팁을 드리자면, 사이클은 넉넉히 뒤쪽에서 구하는게 오류도 적게나고 맞는거같네요. 계속 동전의 갯수 A_k(제일큰수) 다음수 부터 사이클 구해서 할랬는데, 아무래도 초반에는 좀 variation이 많은가봐요. 넉넉하게 한 2000개정도 배열로 구해서 불값 저장해놓고, 1000부터 사이클 + - 900개 잡아놓고 구해서 푸니깐 이제 오류안나네요 ㅜㅜ

mosw7   1년 전

오 감사합니다. 바빠서 손을 안 대고 있었는데 다시 한 번 풀어봐야겠네요.

사이클 찾는 알고리즘을 휴리스틱하게 조절하면 풀린다는건 알겠는데,

수학적으로 어떻게 풀어야 deterministic하게 풀린다는 감이 안 오니까 답답하네요 ㅠㅠ

ㅋㅋ 저도 첨에 관계식 찾아볼려고 노력해봤는데 ㅋㅋ 글쓴분 말씀하신것 (ai+ak) 로 생각했는데, 아닌경우도 넘 많고 아주 기본적인것 외에는 결정짓기가 어렵더군요. 한 이틀 매달리다가 관계식 찾는것 포기했어요 ㅋㅋ

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