백준 9625-python 풀이

전형적인 dp문제

버튼을 누르는 횟수 별 a와 b횟수를 표로 정리하면

금방 해결방법을 찾을 수 있다.

 

/누르는 횟수	0	1	2	3
결과	A	B	BA	BAB
A개수	1	0	1	1
B개수	0	1	1	2

 각각의 a,b 개수 별로

현재 인덱스의 개수 = 전 인덱스 개수 + 전전 인덱스 개수

의 규칙임을  한 눈에 알 수 있다.

 

---

 

# https://www.acmicpc.net/problem/9625

# 전형적인 f(n) = f(n-1) + f(n-2) 구조임
# 입력 : 버튼 눌리는 횟수: k
# 출력 : 사용자가 k번 눌렀을때 결과창에 뜬 a 개수와 b의 개수

k = int(input())

#버튼을 누른 횟수 만큼 a횟수와 b횟수를 각각 나누어 배열로 정리해 보자면 다음과 같다.
#클릭:0  1
a = [1, 0]
b = [0, 1]


def find_a_and_b_count(k):
    if k == 0:
        return a[0], b[0]
    if k == 1:
        return a[1], b[1]
    else:
        #k는 46까지
        for i in range(2, 46):
            a.append(a[i - 1] + a[i - 2])
            b.append(b[i - 1] + b[i - 2])
        return a[k],b[k]

count_a, count_b = find_a_and_b_count(k)
print(count_a, count_b)

---

 

9625번: BABBA