[백준 9625번] [🥈5] BABBA (python)

백준 사이트 링크

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

예제 입력 1

1

예제 출력 1

0 1

예제 입력 2

4

예제 출력 2

2 3

예제 입력 3

10

예제 출력 3

34 55

---

풀이

문제에서 요구하는 것은 A의 개수와 B의 개수를 구하는 것으로 문자열이 K번째에서 AB로 바뀌기 위해서는 K-1번째까지 A의 개수와 B의 개수가 모두 같아야한다. 그리고 K번째에서 바뀌는 것은 A의 개수와 B의 개수가 서로 바뀌는 것이다. 즉, K번째에서 A의 개수와 B의 개수가 서로 바뀐다면, K-1번째까지 A와 B의 개수는 서로 같아야한다.

따라서 K=1일때 A의 개수와 B의 개수는 각각 1과 0이다.

K=2일때 A의 개수와 B의 개수는 각각 0과 1이다.

K=3일때 A의 개수와 B의 개수는 각각 1과 1이다.

K=4일때 A의 개수와 B의 개수는 각각 1과 2이다.

K=5일때 A의 개수와 B의 개수는 각각 2와 3이다.

따라서 입력받은 K번째에서 A의 개수와 B의 개수를 차례대로 출력하면 된다.

코드

ver(1)

# n을 입력 받음
n = int(input())

# a 리스트를 n+1 크기로 생성하고, 0으로 초기화
a = [0]*(n+1)

# a[1]을 1로 초기화
a[1] = 1

# a[i]를 i-1번째와 i-2번째의 합으로 계산
for i in range(2,n+1):
    a[i] = a[i-1] + a[i-2]

# a[n-1]과 a[n]을 출력
print(a[n-1],a[n])

ver(2)

n = int(input())  # 입력값 n을 받아옴
a = [0]*(n+1)  # a 리스트를 생성하고 0으로 초기화
a[1] = 1  # a[1]의 값을 1로 설정

for i in range(2,n+1):  # i가 2부터 n까지 반복
    a[i] = a[i-1] + a[i-2]  # a[i]를 a[i-1] + a[i-2]의 합으로 갱신

print(a[n-1],a[n])  # a[n-1]과 a[n] 출력