[백준] 18222 투에-모스 문자열

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

과정이 반복될수록 2의 제곱만큼 자릿수가 증가하는 규칙이 있어 초기 몇번째 값을 토글하여야 하는지 찾는 방식으로 접근했습니다.

2) 알고리즘

• 분할정복

3) 풀이 코드

사용 언어 - Python

import sys
import math
sys.stdin = open('input.txt')

K = int(sys.stdin.readline())           # 찾아야하는 자릿수
patterns = '0110'                       # 가장 앞의 4자리

sign = 0                                # 반전 여부
while K >= 4:                           # 4자리 이상이면 반복
    if sign:                            # 반전 여부 토글
        sign -= 1
    else:
        sign += 1

    n = int(math.log2(K))               # 현재 자릿수보다 작거나 같은 2의 제곱값 빼기
    K = K - 2**n

    if not K:                           # 0이 되면 2의 (n-1) 제곱 다시 더하기
        K = 2**(n-1)

print(int(patterns[K-1]) ^ sign)        # 초기 몇번째 자리의 값을 토글

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

규칙을 찾는데 다소 오랜 시간이 걸렸습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/18222

18222번: 투에-모스 문자열

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다