[BaekJoon] 백준 9625 BABBA (Python / 파이썬)

BaekJoon 백준 9625 BABBA 문제는 화면에 A가 표시된 기계의 버튼을 누르면 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다. 버튼을 K번 눌렀을 때, A와 B의 개수를 구하는 문제이다. 메모이제이션, DP 동적 계획법 알고리즘 문제이며, 난이도는 Bronze 1이다.

 

BaekJoon 9625 BABBA 문제 정보

출처

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

알고리즘 분류

- 동적 계획법(다이나믹 프로그래밍) DP Dynamic Programming, 메모이제이션 memoization, 수학, 구현

난이도

- 브론즈 1 / Bronze 1

 

BABBA 문제 요약

• 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.
• 기계를 발견했을 때, 화면에는 A만 표시되어 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그다음에는 BAB, 그리고 BABBA로 바뀌었다.
• 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다.
• 버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개인지 구하여 출력한다. (1 ≤ K ≤ 45)

 

시간 초과, 메모리 초과 발생

맨 처음 시도에는 시간 초과가 발생했는데, 재귀 함수를 사용했기 때문이다. 이는 엄청난 중복 호출이 발생하기 때문에 시간이 오래 걸리고 백준 9625번 문제의 시간제한에 만족하지 못합니다.

 

그래서 두 번째에 DP 다이나믹 프로그래밍 알고리즘을 사용해야 한다는 것을 깨닫고, A와 B의 글자를 memo에 저장하여 memo [K]를 구했는데, 메모리 초과가 발생했습니다.

 

# 메모리 초과 > A, B 구성을 memo에 저장
def change(K):
    global memo
    if K < len(memo):
        return memo[K]
    else:
        memo.append(change(K - 1) + change(K - 2))
        return memo[K]


memo = ['A', 'B', 'BA']  # index번 눌렀을 때 화면의 글자
rst = change(int(input()))
print(f"{rst.count('A')} {rst.count('B')}")

 

 

이러한 재귀 함수의 시간적 단점을 보완한 프로그래밍 기법이 바로 DP 동적 계획법과 이의 핵심 기술인  메모이제이션 기법인데요, 성능, 실행 속도 향상을 위해 중요한 기술이므로 한 번 읽어보시면 큰 도움이 될 것입니다.

 

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

DP Dynamic Programming 동적 계획법 알고리즘과 예제

DP Dynamic Programming 동적 계획법 알고리즘과 예제

 

문제 풀이 과정

1. 동적 계획법의 핵심 기술인 메모이제이션 기법을 사용하기 위해 버튼을 index번 눌렀을 때 (A의 개수, B의 개수) 튜플을 원소로 갖는 memo 리스트를 선언한다.
2. 버튼을 0번 누르면 A, 1번 누르면 B 이므로 memo [0] = (1,0), memo [1] = (0,1)을 저장한다.
3. 버튼을 K번 눌렀을 때 A의 개수는 K-1번 눌렀을 때 A의 개수 + K-2번 눌렀을 때 A의 개수, B의 개수는 K-1번 눌렀을 때 B의 개수 + K-2번 눌렀을 때 B의 개수라는 규칙을 찾을 수 있다.
4. 4번에서 알아낸 규칙을 식으로 표현하면, memo [K] = (memo [K - 2][0] + memo [K - 1][0], memo [K - 2][1] + memo [K - 1][1])이다.
5. 위 규칙을 이용하여 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개인지 구하여 출력한다.

 

코드 및 설명

• memo [] - index번 눌렀을 때 (A의 개수, B의 개수) 튜플을 저장하는 리스트

K = int(input())
memo = [(1, 0), (0, 1)]
for i in range(2, K + 1):
    memo.append((memo[i - 2][0] + memo[i - 1][0], memo[i - 2][1] + memo[i - 1][1]))

print(f'{memo[K][0]} {memo[K][1]}')

---

문제를 많이 풀 수록 DP가 얼마나 효율적인 지 조금씩 느끼고 있다.

 

BaekJoon 백준 9625 BABBA 문제를 파이썬 python의 동적 계획법 DP Dynamic Programming(다이나믹 프로그래밍), memoization 메모이제이션 기법을 사용하여 풀어보았다. 난이도는 Bronze 브론즈 1이다.