(백준) 9625번: BABBA 파이썬 풀이(DP풀이)

<포스팅 요약>

1. 문제풀러가기

2. 문제 해결 코드

3. 로직 분석

---

1. 문제풀러가기

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

9625번: BABBA

 

문제 해석:

- A => B로 바뀜, B => BA로 바뀜

- 처음에 A가 출력되어있는 상태에서 시작

예)

0번 눌렀을때 => 결과 : A

1번 눌렀을때 =>A가 B로 바뀌므로 => 결과 : B

2번 눌렀을때 =>B가 BA로 바뀌므로 => 결과 : BA

3번 눌렀을때 => B는 BA로, A는 B로 바뀌므로 => 결과 : BAB

4번 눌렀을때 => B는 BA로, A는 B로, B는 BA로 바뀌므로 => 결과 BABBA

---

2. 문제 해결 코드

코드 (성공)

import sys

input = sys.stdin.readline

k = int(input())

dp = [0 for _ in range(k+1)]
dp[0] = (1, 0)
dp[1] = (0, 1)

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

print(dp[k][0], dp[k][1])

 

메모리 초과인 코드 (실패)

import sys

input = sys.stdin.readline

k = int(input())

dp = [0 for _ in range(k+1)]
dp[0] = "A"
dp[1] = "B"

for i in range(2, k+1):
    dp[i] = dp[i-1]+dp[i-2]

print(dp[k].count("A"), dp[k].count("B"))

 

처음에 아래코드로 돌려서 메모리 초과가 나와 

위의 성공한 코드로 바꿔줬다. 

로직은 똑같지만 count내장함수를 사용해서 메모리 초과가 뜨는것 같다.

 

---

3. 로직분석

- 뭔가 규칙이 있는것 같다 싶으면 DP문제이다. ** 아래 표 참고

 

실버5 문제라서 그런지 규칙을 매우 쉽게 찾을 수 있었다.

클릭횟수	0	1	2	3	4	5
화면	A	B	BA	BAB	BABBA	BABBABAB
A,B개수	(1,0)	(0,1)	(1,1)	(1,2)	(2,3)	(3,5)

위의 표를 보면 

클릭 횟수 2 = 클릭횟수 1 + 클릭횟수 2 = "BA" =>(1+0, 0+1)

클릭 횟수 3 = 클릭횟수 2 + 클릭횟수 1 = "BAB" =>(1+0, 1+1)

.

.

.

점화식으로 표현하면,

dp[0]="A", dp[1]="B", n>=2일때 dp[n]=dp[n-1]+dp[n-2] 이다.