BABBA

배경 아이디어

CS 과목 중 계산이론과 같은 과목을 수강했다면, 뭔가 익숙한 문제 내용이라고 느낄 수 있다.
A -> B, B -> BA 의 규칙은 상태를 정의하는 것으로 이해할 수 있다.

규칙을 정리하자면, A 는 자기자신을 만들지 못하고, B 는 A 와 B 모두를 하나씩 만든다. 버튼을 1번부터 4번까지 누르는 과정을 적어보면 이 규칙은 간단한 수학적 규칙을 나타내는 것을 알 수 있다.

횟수	(A, B)	변화
0	(1, 0)
1	(0, 1)	(-1, +1)
2	(1, 1)	(+1, 0)
3	(1, 2)	(0, +1)
4	(2, 3)	(+1, +1)

*표로 만들면 더 이해가 쉬울 줄 알았으나 오히려 헷갈릴 수 있겠다는 생각도 든다...

정리하자면, 버튼을 누를 때마다 A 의 개수는 온전히 B 의 개수에 추가되며, B 의 개수는 기존의 B 의 개수를 유지하며, 같은 개수만큼 A 에 추가된다.
간단한 수식으로 정리하면 다음과 같다.

(A, B) --(클릭)--> (B, A+B)

버튼을 K 번 눌렀을 때, A 와 B 의 개수는 K-1 번 눌렀을 때의 (B, A+B) 라는 걸 알 수 있다.

---

코딩

K = int(input())

m = {
    0: (1, 0),
    1: (0, 1),
}

for i in range(2, K + 1):
    A, B = m[i - 1]
    m[i] = (B, A + B)

print(*m[K]) # 튜플 분해 반환

---

후기

문제에서 A 와 B 의 변환 로직을 직접 언급하기 때문에 해당 로직을 dp 의 매개체로 활용하는 방식으로 접근할 가능성이 있다. 계산이론을 배웠거나, "상태"라는 개념에 대해 인지하고 있는 상태가 아니라면 충분히 발생할 수 있는 상황이라고 생각한다. 별 생각없이 변환 로직을 중점적으로 파고드는 불상상가 생길 수 있는 문제이다.

처음에는 변환 로직에 집중했지만, 곧 의미가 없는 액션임을 깨닫고, 곧바로 변환 과정에서의 규칙성을 찾는 것을 시도했다.