✏️ 1003번

문제

💡 문제 아이디어

• f(5) 까지 계산하면 위와 같이 된다
• 즉, 0과 1의 개수는 각각 f(n-1) + f(n-2) 개수와 같다

👀 풀이

# 1003

import sys

T = int(sys.stdin.readline())

answers = []

for _ in range(T) :
    z_cnt = [1,0]
    o_cnt = [0,1]

    N = int(sys.stdin.readline())

    if N > 1 :
        for i in range(2,N+1) :
            z_cnt.append(z_cnt[i-1] + z_cnt[i-2])
            o_cnt.append(o_cnt[i-1] + o_cnt[i-2])
    answers.append(f'{z_cnt[N]} {o_cnt[N]}')

for a in answers :
    print(a)

✏️ 1904번

문제

💡 문제 아이디어

N 일 때 ,,,,

• N-2 에서 '00'을 붙이거나
• N-1 에서 '1' 을 붙이는 경우

즉 , f(N) = f(N-2) + f(N-1) 가 된다

👀 풀이

# 1904

import sys

N = int(sys.stdin.readline())

arr = [0,1,2]


if N > 2 :
    for i in range(3,N+1) :
        arr.append((arr[i-2] + arr[i-1]) % 15746)
        
print(arr[N])

이 때 중요한 것은 for 문 안에서 append 할 때 마다 15746 을 나누는 것이다. 마지막에 나누는 것이 아닌 for 문 과정에서 나누는 이유는 N 이 1이상 1,000,000 이하이이기 때문..!! 나누지 않고 그냥 더한 값을 그대로 항에 저장하면 arr[i] 는 굉장히 큰 값을 가지게 될 것이고 그렇게 되면 컴퓨터가 표현할 수 있는 최대 크기를 넘을 수도 있다.