728x90
투에-모스 문자열
문제
0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다.
X는 맨 처음에 "0"으로 시작한다.
X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다.
X의 뒤에 X'를 붙인 문자열을 X로 다시 정의한다.
2~3의 과정을 무한히 반복한다.
즉, X는 처음에 "0"으로 시작하여 "01"이 되고, "0110"이 되고, "01101001"이 되고, ⋯
의 과정을 거쳐 다음과 같이 나타내어진다.
"011010011001011010010110011010011001011001101001⋯⋯"
자연수 k가 주어졌을 때 X의 k번째에는 무슨 문자가 오는지 구하여라.
입력
첫 번째 줄에 자연수 k (1 ≤ k ≤ 1018) 가 주어진다.
출력
첫 번째 줄에 k번째에 오는 문자를 출력하라.
뭔가 쉽다고 생각했는데 메모리가 문제... 이 문제를 어떻게 해결해야할까?
import sys
k = int(sys.stdin.readline())
tm_st = "0"
while(len(tm_st) < k):
co_st = tm_st
co_st = co_st.replace("1","2")
co_st = co_st.replace("0","1")
co_st = co_st.replace("2","0")
tm_st += co_st
print(tm_st[k-1])
재귀로 풀어야한다고해서 재귀식을 생각해 보았으나 생각이 나지않아 찾아 보았다.
그래서 찾은 식이
t0 = 0
t2n = tn
t2n+1 = 1 - tn
import sys
N = int(sys.stdin.readline())
# 재귀식 사용
# t0 = 0
# t2n = tn
# t2n+1 = 1 - tn
def sol(N):
if N == 0:
return 0
elif N % 2:
return 1 - sol(N//2)
else:
return sol(N//2)
# 시작이 0이라서 1을 빼고
print(sol(N - 1))
'@@@ 알고리즘 > 백준 스터디' 카테고리의 다른 글
10844 - 해결 (0) | 2021.08.03 |
---|---|
14713 - 해결 (0) | 2021.08.02 |
7569 - 답 확인 (0) | 2021.08.01 |
10703 - 해결 (0) | 2021.08.01 |
15903 - 해결 (0) | 2021.07.31 |