2개의 댓글이 있습니다.
-
-
riceluxs1t -
감사합니다! 글작성하고 나서 글을 적다보니 스스로 해법을 찾은것 같습니다.
9년 전 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 입니다. 이렇게 반복되는 수열이 있는데
아래는 편의상 나눈거고 사실은 10^12 길이의 수열이 입니다. 출력 해야할 답은,
n번째 항을 상대방이 낸다고 가정할 때, 이기기 위해서 내야할 move 입니다. (묵, 찌 혹은 빠).
R P S PSR SRP PSRSRPRPS SRPRPSPSR PSRSRPRPSSRPRPSPSRRPSPSRSRP ...
아래는 제 접근/사고과정 입니다.
메모리 초과가 납니다. 아마 f(n) = 답. 식의 O(1) 답을 요하는 것 같은데 (순수 수학..공식 도출)
일단 맨 처음 접근한 방식이
10^12의 답 문자열을 미리 생성 한 뒤 n번째 항에 대한 승리 요건 반환 입니다. 문자열 생성은 파이썬의 문자열 합치는데 소요되는 오버헤드를 제외하곤 길이에 대해 O(n)안에 생성 가능 합니다. 하지만 이런 문자열을 저장하는데 이미 메모리 초과가 나는 것 같습니다..
2) 두번째는 수열의 길이가 1, 1, 1, 3, 3, 9, 9, 27, 27, 81, 81, ...
즉 첫번째 항을 제외하곤 어떤 항과 그다음 항의 길이 합이 2*3^(n-1) 임에 착안해
몇번째 항에서 답이 존재하는지를 찾은 뒤 n번째 move에 대한 답을 출력하는 건데..이것도 메모리 초과가 나는것 같습니다.
이 방법은 일단 해당 항을 찾는데 O(logn). 1초 시간제한안에 가능 한것 같습니다만.. n이 클 시 여전히 해당 항에 대한 문자열의 길이가 길기 때문에 메모리 초과가 나는 것 같습니다.
도움 부탁드립니다 ㅜㅜ
9년 전