728x90
동적 프로그래밍(Dynamic Programming)을 사용하여 0과 1로 이루어진 특정 수열을 생성하고, 주어진 수열의 각 숫자들 중 0과 1의 개수를 구할 수 있다.
피보나치 n에서 0 호출횟수 = (피보나치 n-1에서 0 호출횟수) + (피보나치 n-2에서 0 호출 횟수)
피보나치 n에서 1 호출횟수 = (피보나치 n-1에서 1 호출횟수) + (피보나치 n-2에서 1 호출 횟수)
이므로
점화식
- count_zero[i] = count_zero[i-1] + count_zero[i-2]
- count_one[i] = count_one[i-1] + count_one[i-2]
이런 점화식을 생각할 수 있다.
t = int(input()) # 테스트 케이스의 수 입력
def count_ways(n):
count_zero = [1, 0] # 0의 개수를 저장하는 배열 초기화
count_one = [0, 1] # 1의 개수를 저장하는 배열 초기화
for i in range(2, n+1): # 2부터 n까지 반복
count_zero.append(count_zero[i-1] + count_zero[i-2]) # 0의 개수를 계산하여 배열에 추가
count_one.append(count_one[i-1] + count_one[i-2]) # 1의 개수를 계산하여 배열에 추가
return count_zero[n], count_one[n] # n에 대한 0의 개수와 1의 개수를 반환
# 입출력
results = [] # 결과를 저장할 리스트 초기화
for _ in range(t): # 테스트 케이스 수만큼 반복
n = int(input()) # 각 테스트 케이스의 입력값을 받음
results.append(count_ways(n)) # 결과 리스트에 해당 테스트 케이스의 결과 추가
for r in results: # 결과 리스트의 각 결과에 대해
print(r[0], r[1]) # 0의 개수와 1의 개수 출력
함수 `count_ways(n)`은 매개변수로 주어진 `n`에 대해 0과 1로 이루어진 수열을 생성하고, 해당 수열의 각 숫자들 중 0의 개수와 1의 개수를 반환한다.
0과 1로 시작하는 기본적인 수열을 만들고, 그 이후에는 피보나치 수열의 아이디어를 사용하여 새로운 숫자들을 계산한다.
즉, `count_zero[i]`는 `count_zero[i-1]`과 `count_zero[i-2]`의 합이 되며, `count_one[i]`도 동일한 방식으로 계산된다.
728x90
