|
m = int(input())
k = 0
leng = 3
while leng < m :
k = k + 1
leng = 2 * leng + 3 + k
def DAC(x, l, n) :
if x == 0 :
if n == 1 :
return 'm'
else :
return 'o'
l = (l - 3 - x) // 2
x = x - 1
if n <= l :
return DAC(x, l, n)
elif n == l + 1 :
return 'm'
elif n > l + x + 4 :
return DAC(x, l, n - l - x - 4)
else :
return 'o'
print(DAC(k, leng, m))
|
n의 range가 10억이므로 순열을 직접 만들어서는 메모리 초과가 나올 것이다.
순열을 직접 만들지 않고 길이와 구성만 다루는 접근이 필요하다.
S(k)는 세 부분으로 나눌 수 있다. 왼쪽 S(k-1), 가운데 moo...oo, 그리고 오른쪽 S(k-1)
그렇다면 n보다 큰 S(k)가 있을 때, n번째가 셋중 어디에 위치하느냐에 따라 분기하는 재귀함수를 만들 수 있다.
1.
n이 S(k-1)의 길이 L(k-1)보다 작다면, S(k)의 n번째는 S(k-1) 안에서도 n번째의 위치에 있을 것이다.
f(S(k), n) = f(S(k-1), n) if n <= L(k-1)
2.
n이 L(k-1)의 다음 번째라면 moo...ooo의 첫글자이므로 'm'이다.
f(S(k), n) = 'm' if n = L(k-1) + 1
3.
n이 L(k-1) + k + 4 이상이라면, S(k)의 오른쪽에 위치한 S(k-1)의 안에 있다.
그리고 그 안에서의 순서는 n번째가 아니라 n - L(k-1) - k - 4 번째일 것이다.
f(S(k), n) = f(S(k-1), n - L(k-1) - k - 4) if n >= L(k-1) + k + 4
4.
위 123에서 따져주지 않은 경우는 가운데 moo...ooo의 'o'들이다.
f(S(k), n) = 'o' else
이를 코드로 구현해주면 중간에 moo...ooo에 걸려 탈출하거나, 재귀를 반복하여 S(0) = 'moo'까지 거슬러 올라가 결과를 출력한다.
(매 k-1마다 L(k-1)를 새로 구하긴 까다로우므로, 편의상 재귀함수의 변수 입력에 k뿐 아니라 l(k)도 같이 넣었다.)
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 1933 스카이라인 (스택과 큐를 곁들인) (0) | 2021.11.19 |
|---|---|
| 파이썬 백준 9935 문자열 폭발 (0) | 2021.11.18 |
| 파이썬 백준 13705 Ax+Bsin(x)=C (0) | 2021.11.17 |
| 파이썬 백준 3955 캔디 분배 (0) | 2021.11.17 |
| 파이썬 백준 1517 버블 소트 (0) | 2021.11.17 |