백준/ Silver3 문제 , 백준 파이썬 9095, 1, 2, 3 더하기

백준/ Silver3 문제 , 백준 파이썬 9095, 1, 2, 3 더하기

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

-------------------------------------------------------------------------------------------

<난이도 체감>
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있었지만 이해했다.
3. 아직 헷갈리는 부분들이 있음
4. 이해 못함

 

 

 

 

<문제 출처>

 

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

------------------------------------------------------------------------------------------------------------------------------

 

 

이전 2193 이친수 문제 처럼 경우의 수들을 나열해보면 규칙이 눈에 보인다.

 

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Silver3-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-2193-%EC%9D%B4%EC%B9%9C%EC%88%98

백준/ Silver3 문제 , 백준 파이썬 2193 , 이친수

 

 

 

n=1 일 때, 1 => 1가지

 

n=2 일 때, 1+1, 2 => 2가지

 

n=3 일 때, 1+1+1, 1+2, 2+1, 3 => 4가지

 

n=4 일 때, 1+1+1+1,  1+1+2,  1+2+1,  2+1+1,  2+2 ,  1+3 ,  3+1 => 7가지

 

n=5 일 때, 1+1+1+1+1,  1+1+1+2,  1+1+2+1,  1+2+1+1,  2+1+1+1,  1+2+2,  2+1+2,  2+2+1,  1+1+3,  1+3+1,  3+1+1,  3+2,  2+3  => 13가지

 

 

 

 

 

규칙을 보면

 

n=4 일 때 ,7가지는 앞의 n=1, 2 ,3 일때 1+2+4가지를 더한 값과 같다.

 

n=5 일 때, 13가지는 앞의 n=4,3,2 일 때 2+4+7 가지를 더한 값과 같다.

 

 

이것을 일반화 해보면 T(n) = T(n-1) + T(n-2) + T(n-3) 한 값이다.

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

정답