mosw7   5년 전

돌 게임 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   5년 전

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

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

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

mosw7   5년 전

네 감사합니다!

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

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

hananakajima   5년 전

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

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

mosw7   5년 전

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

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

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

hananakajima   5년 전

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

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