https://programmers.co.kr/learn/courses/30/lessons/12946
-
flow
처음에 당연히 횟수 구하는 줄 알고 ㅋㅋ 점화식이 뭐였더라 회상함.. f(n) = 2f(n-1) + 1 임을 인지했지만 그게 아니라 방법을 return 하는 문제였음..
이런 문제는 처음 봤는데 의도를 생각해봤을 때, 당연히 규칙이 있겠지 생각을 함.
점화식이 만들어지는 원리를 생각해보면 n-1 개 쌓는 방법으로 옮겨놓고 제일 큰 하나(n번째)를 끝에 옮겨 놓고 다시 n-1개 탑을 옮기면 n 개의 탑이 쌓이는 방식..
그러면 쌓는 방법도 f(n-1)og, 1, f(n-1)og 와 같은 규칙이 있지 않을까 해서 계속 살펴본 결과
f(n)을 n개 쌓는 방법이라 할때, f o g(n) + (1,3) + f o h(n) (g: 존재하는 2와 3 모두 바꿈 2->3, 3->2, h: 존재하는 1과 2 모두 바꿈 1->2, 2->1)
으로 만들어지는 값이 f(n+1) 임을 깨달았음.
시간복잡도 O(n) 이지만 n이 15이하 자연수.. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A23.py
