[백준, 파이썬, 18222번] 투에-모스 문자열

 

풀이

• 문제에 나와있는 것처럼 값을 만들어 낸 다음 찾는 형식으로 한시간 넘게
   가지치기를 하면서 생 고생을 했지만 결국은 2% 시간초과...
• 이후 힌트를 얻기 위해 구글링을 했을 때 투에-모스 문자열의 점화식이 있다는 걸 확인

출처: https://ko.wikipedia.org/wiki/%ED%88%AC%EC%97%90-%EB%AA%A8%EC%8A%A4_%EC%88%98%EC%97%B4

• 해당 점화식을 활용해 푼 결과 간단히 해결... (좀 애바다...)

 

정답 코드

def tue(n):

    if n == 0: return 0

    elif n%2: return 1-tue(n//2)

    else: return tue(n//2)

print(tue(int(input())-1))

 

한참 고생했지만 실패한 코드

• 아래 코드는 k의 길이 중간 까지만 찾고
• 해당 idx의 반대 값을 구하는 형식으로 해결하려 했지만 실패... 

k = int(input())

cnt = 0

result = '0'

if k == 0: print(1)

else:

    while True:

        cnt += 1

        tmp = ''

        for i in result:

            if i == '0': tmp += '1'

            else: tmp += '0'

        result += tmp

        if len(result) >= k//2: 

            idx = k//2-1

            if result[idx] == '0': print(1)

            else: print('0')

            break