[BOJ][Python] 9625번 - BABBA[구현 - 실버 5티어]

알고리즘 태그

[구현]

태그 설명

아이디어를 코드로 바꾸는 능력

 

문제

백준 문제 - BABBA

링크: BABBA

문제설명

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.
기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.
버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

 

문제를 처음 읽으면 굉장히 난해하다는 느낌이 든다. 그래서 while문도 돌려보고 이것저것 했는데, 이건 아니다 싶어서 결국,, 구글에 의존해서 풀게 되었다.

문제의 수학적 공식(?) 규칙은 이러했다.

A -> B -> BA -> BAB -> BABBA -> BABBABAB -> BABBABABBABBA
1 ->  0 ->  1  ->  1  ->     2     ->       3        ->           5              : A갯수 
0 ->  1 ->  1  ->  2  ->     3     ->       5        ->           8              : B갯수

특징이 보이는가? 내가 구하고자 하는 값의 바로 전단계의 값과 전전단계의 값의 합이다.

그러나 더 나아가면 A의 갯수는 B갯수의 바로 전단계에 해당한다

예로 들면 맨 마지막(BABBABABBABBA)을 보면 B의 갯수는 전단계와 전전단계의 합이고, A의 갯수는 바로 내가 계산하고자 하는 B갯수의 바로 전단계임을 알 수 있다.  결국 피보나치였다..

항상 문제풀면서 느끼는데, 이런 규칙을 잘 찾아내는 사람들은 대단한거같다..😁

📃 소스코드 및 설명

k = int(input())
result = [0] * (k+1)
result[1] = 1
for i in range(2, k + 1):
  result[i] = result[i-1] + result[i-2]
print(result[k-1], result[k])

 

다른 사람의 풀이 중 좀 더 직관적인 코드가 있어서 첨부한다.

📃 소스코드 및 설명

a = [0] * (k+1)
a[0] = 1
a[1] = 0
 
b = [0] * (k+1)
b[0] = 0
b[1] = 1
 
for i in range(2, k+1):
    a[i] = a[i - 1] + a[i - 2]
    b[i] = b[i - 1] + b[i - 2]
print(a[k], b[k])