백준 1, 2, 3 더하기 5 문제 분석

일단 문제를 확인해보면 1부터 3까지 총 3 가지 수로 주어진 N의 더하기 경우의 수를 구하는 문제임을 알 수 있다.

조건이 있는데 연속된 수를 사용하면 안 된다란 조건이 있다. => 곧 힌트란 의미.

먼저 이를 어떻게 구하는 지 고민을 해보면 완전탐색을 생각할 수 있다.

처음 태블릿으로 적었는데 진짜 못 그렸다... 아이패드 돌려줘;;

각 경우의 수가 총 2개이다.

1 깊이에서 3개, 2 깊이에서 2개씩 총 6개, 3 깊이에서도 2개씩 총 6*2 12개이다. 4 깊이에서는 24개

결국 깊이에서의 경우의 수가 3, 6, 12, 24 순으로 늘어난다. 무슨 수열인지는 모르겠지만 자신의 앞의 수 * 2씩 늘어난다. 딱 봐도 엄청 느리다. 

그래도 수식을 구해야하니까 수열에 공통적으로 3이 곱해져 있으니, 앞으로 빼보니 3*2^n 이다. 문제에서는 n이 100,000보다 작거나 같다고 하니 3*2^n은 계산기도 오버플로우가 난다. 2^100 만 해도 1,267,650,600,228,229,401,496,703,205,376가 나오니 시도조차 하면 안 되는 방법이다.

어차피 완전탐색을 그리다보면 같은 경우의 수를 탐색하며, 똑같은 상태를 매번 계산한다는 점이 느껴진다. 그럼으로 DP로 풀 수 있다고 느껴진다고 해야한다.( 사실 문제의 유형을 보고 풀어서 ... )

이 문제는 조건이 있었다. 만약 없다면 어떻게 풀까?

조건없이 푸는 경우

5를 구한다면 2, 3, 4의 수를 더하면 된다.

근데 이 문제는 연속된 경우를 피해야 한다. 어떻게 피할 수 있을까? 일단 일차원 배열의 경우, 안에 중첩된 경우를 분간하지 못한다.

# 느낌

3차원으로 dp 그리기

# 1의 경우

모양이 똑같다.

# 2의 경우

# 3의 경우

# 4의 경우

근데 표를 돌려본다면?

테이블이 트리 모양이랑 똑같다.

신기하다