백준 9625 python

백준 9625 python

기본적으로 첫 시도로는 무식한 방법(브루트포스)을 선호한다. 문자열을 그대로 만들자

def get_next_brute(string):
	new_chars = [] # new_string으로 해도 되지만 문자열 덧셈은 시간을 많이 잡아먹는다
	for c in string:
		if c == "A":
			new_chars.append("B")
		if c == "B":
			new_chars.append("BA")
	return "".join(new_chars)

시행횟수가 증가할 때마다 2배씩 길이가 증가하기 때문에 45까지하면 메모리가 터질 것이다.

개선하자.
직접 계산할 필요없이 A와 B의 개수만 세도 괜찮을 것 같다.

def get_next(a_cnt, b_cnt):
	a_cnt = b_cnt # b => b,a가 되기 때문에 a가 생김
	b_cnt = a_cnt + b_cnt # 
	return a_cnt, b_cnt