문제 링크
https://www.acmicpc.net/problem/17297
🕒 Python 풀이시간: 60분
dp=[]
dp.append(6)
dp.append(14)
M=int(input())
while True:
k=dp[-2]+dp[-1]
dp.append(k)
if k>M:
break
messi=["Messi ","Messi Gimossi "]
if M<=14:
index=1
else:
index=len(dp)-1
front=index-1
back=index-2
wordIndex=M
while True:
if index==0 or index==1:
answer=messi[1][wordIndex-1]
if answer==" ":
print("Messi Messi Gimossi")
else:
print(answer)
break
if wordIndex>dp[front]:
index=back
wordIndex-=dp[front]
else:
index=front
front=index-1
back=index-2피보나치 문자열: Messi의 비밀을 풀어라! ⚽️🔍
Messi와 Messi Gimossi의 문자열을 피보나치 수열과 유사하게 이어붙여서 나오는 문자열의 M번째 자리 문자를 구하는 문제이다. 해당 문자열을 직접 이어붙여서 만들려고 한다면 메모리 초과가 나오기 때문에 불가능하다.
그렇다면 이를 함축하여 풀어야되는데 이 때, 문자열의 길이를 생각하였다. 문자열의 길이로 이어붙여가면서 문자열의 길이를 dp로 누적하고 역으로 이를 분해해가면서 어떤 영역에 몇번째에 있는 문자를 구하는지를 구해내는 것이다.
먼저 문제에서 주어진 점화식으로 문자열의 길이를 사용하여 구해나간다. 이 때 우리가 구하는 몇 번째 문자가 포함되는 길이까지만 구하면 된다. 구하고자하는 순번의 문자가 포함된 dp를 구해냈으면 찾아내기만 하면 된다. 우리가 구한 것이 dp의 0과 1안에 있다면 즉 Messi와 Messi Gimossi 문자열 안에 속하면 반복문을 멈춘다. 만약 그렇지 않다면 현재 문자열을 이루고 있는 n-1과 n-2중 어디에 속하는지 파악한다. 만약 앞쪽에 속한다면 현재의 dp의 순번을 앞쪽 dp로 이동시키고 현재 문자의 순번도 그대로 가지고 간다. 만약 뒤쪽에 있다면 dp의 순번을 뒤쪽 dp로 이동시키고 앞쪽의 있는 문자열의 길이 만큼 즉, dp만큼 빼어 앞쪽부터의 순번으로 갱신한다. 그 후, front와 back을 현재 index(=dp)에 맞게 조정하면 된다.
이렇게 Python으로 백준의 "Messi Gimossi" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
