시간 제한이 0.25초로 걸려있는 것이 정직하게 피보나치 돌리면 시간 초과가 뜬다는 것을 암시한 것인가.

dp[i]에는 정수 i를 1, 2, 3의 합으로 나타내는 방법의 수가 담겨있다.
그래서 정수 5를 1, 2, 3의 합으로 나타내는 방법의 수가 궁금하다면, dp[2] + dp[3] + dp[4]가 될 것이다.

크게 두 가지 경우의 수가 있다.

1. 3로 나누어 떨어질 경우
2. 3으로 나누어 떨어질 경우

3번 조건은 언제나 적용할 수 있기 때문에 처음부터 계산하고 시작한다.
2와 3의 공배수 같은 경우는 2와 3 둘 다 나누어 떨어지기 때문에 다른 조건을 만들어야 하나 싶었지만 어차피 dp[]에 저장된 값을 같은 i를 돌고 있을 때 다시 확인하므로 상관이 없다.

이전의 반도체 설계 문제와 동일하게 최장 증가 수열을 구하는 문제다.

2020년 4원 7일 포스트 수정

저 문제 풀 때는 dp가 뭔지도 몰랐다.
이번엔 동적 계획법으로 풀어봤다.
dp[i]에 arr[i]이전의 값들을 비교하며 arr[i]보다 작은 값이 있다면 그 때의 dp[]에 담겨있는 값 + 1을 dp[i]에 넣는다. arr[i]이전의 모든 수에 위 과정을 반복했을 때 가장 큰 수가 dp[i]가 된다.
마지막으로 dp[]에 담겨있는 값 중 가장 큰 값이 최장증가수열의 길이가 된다.