[일반] 프로그래머스 N으로 표현같은거 시간복잡도 어케 계산하나여?

[ㄹㄹ(119.207)]

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42895

이걸 풀긴했는데 시간복잡도를 어케 계산하는지 몰겟어용

여기에 검색해보니까 갤주님  풀이랑 거의 같게 풀었는데, 이때 시간복잡도 계산이 너무 복잡함 ㅜㅜ 주먹구구식으로라도 계산하는 방법이따로 있나요?

갤주 풀이:https://gall.dcinside.com/mgallery/board/view/?id=ps&no=1950&s_type=search_all&s_keyword=N%EC%9C%BC%EB%A1%9C+%ED%91%9C%ED%98%84&page=1

[익명(223.62)]

dp에서 시간복잡도는 대부분 상태공간*한 상태에서 전이할 수 잇는 경우의 수임.

[ㄹㄹ(119.207)]

근데 이게 예를 들어 N=4일때를 구하려면 N<=3 일때 각 집합의 갯수를 알아야 하지 않나요?? 근데 그게 천차만별아닌가 해서영