백준 17297 - Messi Messi Gimossi (Python)

문제

https://www.acmicpc.net/problem/17297

17297번: Messi Gimossi

풀이

#오답, 6을 입력했을 때 공백이 출력됨
n = int(input())
ls = [5,13]
while ls[-1] < n:
    ls.append(ls[-1]+ls[-2]+1)
def f(k,c):
    if k<2:
        return 'Messi Gimossi'[c-1]
    
    if ls[k-1]+1 == c:
        return "Messi Messi Gimossi"
    elif ls[k-1] >= c:
        return f(k-1,c)
    else:
        return f(k-2,c-1-ls[k-1])
print(f(len(ls)-1,n))

재귀함수를 이용하여 풀이하였다.

문자열을 직접 만들어서 구할경우 메모리가 초과되므로 다른 방식을 사용하였다.

 

ls에는 messi(i)의 글자수를 저장하였다.

f(k, c)는  messi(k+1)의 c번째 글자를 의미한다.

함수내에서 점점 k를 줄여나가는 과정을 수행한다.

예를 들어,

messi(3) 은 messi(2) + ' ' + messi(1)이므로 

f(2, 16) = f(0,2) 으로 나타낼 수 있다.

k를 줄여나가면서 0또는 1이 되었을 때, "Messi Gimossi" 의 c번째 글자를 출력하면 된다.

공백의 경우 줄여나가는 과정에서 바로 판단이 되고, Messi Messi Gimossi 를 바로 반환시키면 된다.

 

처음 제출했던 코드는 위와 같은데, 이는 6이 입력되었을 때, 공백을 그대로 출력하여 오답 처리되었다.

따라서, k가 0 또는 1일때 c를 비교하여 6이면 Messi Messi Gimossi 를 출력하는 과정을 추가해주었다.

#정답
n = int(input())
ls = [5,13]
while ls[-1] < n:
    ls.append(ls[-1]+ls[-2]+1)
def f(k,c):
    if k<2:
        if c == 6:
            return "Messi Messi Gimossi"
        else:
            return 'Messi Gimossi'[c-1]

    
    if ls[k-1]+1 == c:
        return "Messi Messi Gimossi"
    elif ls[k-1] >= c:
        return f(k-1,c)
    else:
        return f(k-2,c-1-ls[k-1])
print(f(len(ls)-1,n))