[week02] 백준 5904번 파이썬 풀이

왜 틀렸는지

메모리초과의 늪에서 한참동안 빠져있던 문제였다.

찾는 N의 범위가 1~10억 이기 때문에 배열에 Moo 수열을 만들어서 넣으면 메모리 초과가 뜬다.

그래서 m의 위치만 배열에 집어넣어도 마찬가지로 메모리 초과가 난다.

큰 수를 배열에 넣는 순간 메모리를 많이 잡아먹는 것을 처음부터 생각해서 배열에 넣는 방식말고 다른 방식을 사용했어야 했는데 그러지 못했다.

접근방법

배열에 수열, m의 위치를 넣지 못한다면 n이 Moo수열의 몇 번째 원소인지 어떻게 찾아낼 것인가?

길이를 사용하면 된다 !.!

 

문제에서 주어진 점화식은 S(K) = S(K-1) + (3+K) + S(K-1) 이고

이는 S(K) = 2*S(K-1) + K + 3으로 쓸 수 있다.

그런데 여기서 S 수열을 S 수열의 길이로만 바꿔주면 되기 때문에 동일한 점화식을 만들 수 있다.

L(K) = 2 * L(K-1) + K + 3

이 점화식으로 재귀를 이용해서 풀면 된다.

 

짚어볼 포인트는 원래 재귀를 사용한다면

1. L(K-1)

2. (K+3)

3. L(K-1)

 

이렇게 3개의 구간으로 나눠서 생각해야 하는데, 코드상에서 재귀함수가 돌면서 새로운 L(K) [ 코드에서는 new_l ]를 생성하는 조건이

L(K)가 n보다 작을때이기 때문에 바로 그 다음 재귀에서 L(K-1) [ 코드에서는 l ]은 무조건 n보다 작다. 그러니까 위에서 본 3개의 조건중에 사실은 2개만 보면 된다. 

 

1. L(K-1) < 이 안에는 n이 존재하지 않음

2. (K+3)

3. L(K-1)

1번 구간은 볼 필요가 없다.

2번 구간에서는 m은 맨 처음에만 존재한다.(ex moooo)

3번 구간은 n에서 (l+K+3)을 빼줌으로써 3번 구간을 1번구간처럼 볼 수 있게 하고 재귀를 처음부터 돌리면 된다.

 

아래 코드에 자세한 주석을 써 놓았다

코드

import sys
s0 = ['m', 'o', 'o']
def sol(n, k, l):                # n: Moo 수열의 n번째 글자(찾고자 하는 글자), # k: 차수, # l: 이전 차수의 길이
    # new_l: 새로운 차수의 길이 # 점화식 l(k) = l(k-1) + (k+3) + l(k-1)
    new_l = 2*l + k + 3
    if n <= 3:                   # n이 3 이하일 경우 바로 출력
        print(s0[n-1])
        exit(0)
    if new_l < n:                # new_l이 n보다 작을 경우
        sol(n, k+1, new_l)       # k 차수를 하나씩 늘려준다. new_l이 n을 담을 수 있을 때까지
    else:
        # n은 l보다 무조건 크기 때문에 생각하지 않는다. 원래 3파트로 나눠서 봐야하는데 2파트만 보면 된다.
        if n > l and n <= l+k+3:
            if n-l != 1:         # n-l = 1일때만 'm'이 있고 나머지는 'o'로 채워진다.
                print('o')
            else:
                print('m')
            exit(0)
        else:                    # 1+k+3 바깥에 있는 경우
            # [n - (1+k+3)]을 진행해서 다시 첫번째 part로 돌아온 다음 처음부터 재귀를 돌리기 시작한다.
            sol(n-(l+k+3), 1, 3)
n = int(sys.stdin.readline())
sol(n, 1, 3)