- 유형:
DP-> Recursive랑 DP랑 헷갈리지 말자... 이건DP다. 점화식 알아내는 게 포인트. - 접근 방식: 일단 제한사항에서 최대 8번을 넘을 수 없다는 것이 가장 눈에 띤다. 그러면 8까지 연산해볼 수 있지 않을까? 하는 생각이 든다. (여기까진 맞았었다) 다만 점화식을 잘 생각했어야 한다.
- 점화식: N을 n개 써서 나타내는 법. 예를 들어 n이 3이면 f(1)
+-*//f(2), f(2)+-*//f(1).+-*//는 사칙연산을 한꺼번에 써본 것이다👀
# 의사코드
for i in range(1,n):
f(n) += f(i) +-*// f(n-i)- 주의점:
555와 같이 점화식에 포함되지 않는 원소를 살뜰히 챙기자. 그리고 중복을 피하기 위해 set을 쓰자.