2개의 댓글이 있습니다.
-
-
riceluxs1t -
감사합니다! 글작성하고 나서 글을 적다보니 스스로 해법을 찾은것 같습니다.
11년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
SINCE 2007
감사합니다! 글작성하고 나서 글을 적다보니 스스로 해법을 찾은것 같습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
riceluxs1t
https://algospot.com/judge/problem/read/ANOTHERRPS
^ 문제링크입니다.
신년에도 한문제 한문제 풀고있습니다.
ANOTHERRPC 문제 풀고있는데 문제는 다음과 같습니다.
R, P, S = 묵, 보, 찌일때, 아래와 같은 수열이 반복됩니다.
수열 생성 원리는 처음에 묵 보 찌 이고. 그 다음 상대방이 묵보찌 순서로 낸다고 가정할때 이길 순서가 빠찌묵 입니다. (PSR). 그 다음이 마찬가지로 상대방이 빠찌묵일때 SRP. 여기서 SRP 다음은 처음의 RPS로 돌아가기 때문에 RPS 대신, 처음 부터 전체까지의 수열을 상대방이 냈을 때 이기는 winning seqeunce가 PSRSRPRPS 입니다. 이렇게 반복되는 수열이 있는데
아래는 편의상 나눈거고 사실은 1012 길이의 수열이 입니다. 출력 해야할 답은,
n번째 항을 상대방이 낸다고 가정할 때, 이기기 위해서 내야할 move 입니다. (묵, 찌 혹은 빠).
R P S PSR SRP PSRSRPRPS SRPRPSPSR PSRSRPRPSSRPRPSPSRRPSPSRSRP ...
아래는 제 접근/사고과정 입니다.
메모리 초과가 납니다. 아마 f(n) = 답. 식의 O(1) 답을 요하는 것 같은데 (순수 수학..공식 도출)
일단 맨 처음 접근한 방식이
1012의 답 문자열을 미리 생성 한 뒤 n번째 항에 대한 승리 요건 반환 입니다. 문자열 생성은 파이썬의 문자열 합치는데 소요되는 오버헤드를 제외하곤 길이에 대해 O(n)안에 생성 가능 합니다. 하지만 이런 문자열을 저장하는데 이미 메모리 초과가 나는 것 같습니다..
2) 두번째는 수열의 길이가 1, 1, 1, 3, 3, 9, 9, 27, 27, 81, 81, ...
즉 첫번째 항을 제외하곤 어떤 항과 그다음 항의 길이 합이 2*3n-1 임에 착안해
몇번째 항에서 답이 존재하는지를 찾은 뒤 n번째 move에 대한 답을 출력하는 건데..이것도 메모리 초과가 나는것 같습니다.
이 방법은 일단 해당 항을 찾는데 O(logn). 1초 시간제한안에 가능 한것 같습니다만.. n이 클 시 여전히 해당 항에 대한 문자열의 길이가 길기 때문에 메모리 초과가 나는 것 같습니다.
도움 부탁드립니다 ㅜㅜ
11년 전