BOJ-2193 - Python

2진수 중에 처음이 1로 시작하며 1과 1이 붙어있지 않은 수를 이친수라 할 때, n자리수에 이친수가 몇 개가 있는 지 출력하는 문제. 첫번째 풀이는 반복문을 이용하여 i-1 자리수가 0일 때 1로 수정하여 집합 자료형에 추가하는 방식으로 하였으나 수가 커질 때는 연산의 수가 많아져 이 방법은 포기하게 되었다. 고민 중 이친수의 수가 피보나치 수와 같다는 것을 깨닫고 피보나치 수를 반환하는 함수를 만들어 풀었다.

# 2193
# n = int(input())
# if n <= 2:
#     print(1)
#     exit(0)
#
# first = ('1' + ('0' * (n-1)))
# s = {first}
#
# for i in range(n-1, 1, -1):
#     temp = list(first)
#     if temp[i - 1] == '0':
#         temp[i] = '1'
#         s.add(''.join(temp))
#
#     for j in range(n-1, i-1, -1):
#         if temp[j - 1] == '0':
#             temp[j] = '1'
#             s.add(''.join(temp))
#             temp[j] = '0'
#             continue
# print(len(s))

def f(n):
    if n <= 2:
        return 1
    o, t = 1, 1
    for _ in range(n-2):
        temp = o + t
        o = t
        t = temp
    return temp


n = int(input())
print(f(n))

Written by@hyesungoh
Learning every moment

InstagramGitHubLinkedIn