백준/ Silver 1 문제 , 백준 파이썬 15989 , 1, 2, 3 더하기 4

백준/ Silver 1 문제 , 백준 파이썬 15989 , 1, 2, 3 더하기 4

 

 

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

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

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

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

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

5. 솔루션을 찾아봤는가?

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

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


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
1,2 가지고 더하는 건 금방 경우의 수들을 찾았는데 3 까지 더할때부터 약간 헷갈렸다.
그래도 직접 공책에 경우의 수들을 나열해보면 일정한게 보임.

 

<문제 출처>

 

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

15989번: 1, 2, 3 더하기 4

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

 

 

풀 때 공책에 10까지 경우의 수들을 쫙 나열해 봤는데

 

우선 1과 2 가지고 만들수있는건 금방 보인다.

 

3은 안쓴다 가정하고 1과 2로만 만들 수있는 걸 체크해보자.

 

우선 1로만 만들 수 있는 경우의 숫자는 모든 숫자들이 1가지의 경우만 가진다.

 

그러므로 

 

 

따로 카운트 필요없이 1로 된 dp 를 선언 해준다.

 

범위가 10000 까지이므로 인덱스에 맞춰 10001 크기로 선언

 

이후

 

2부터 

 

2= 2     1가지

 

3= 2+1   1가지

 

4 = 2+1+1   2+2   2가지

 

5 = 2+1+1+1   2+2+1   2가지

 

6 = 2+1+1+1+1   2+2+1+1   2+2+2   3가지

 

7 = 2+1+1+1+1+1   2+2+1+1+1   2+2+2+1   3가지

 

8 = 2+1+1+1+1+1+1   2+2+1+1+1+1   2+2+2+1+1   2+2+2+2   4가지

 

9 = 2+1+1+1+1+1+1+1   2+2+1+1+1+1+1   2+2+2+1+1+1   2+2+2+2+1   4가지

 

10 = 2+1+1+1+1+1+1+1+1   2+2+1+1+1+1+1+1   2+2+2+1+1+1+1   2+2+2+2+1+1   2+2+2+2+2   5가지

 

.

.

.

 

 

이런 식으로 증가 한다.

 

규칙이 보인다.

 

2의 배수일때마다 가짓수가 증가한다.

 

그러므로

 

 

2를 제외하고 4부터 카운트를 해주면 된다.

 

추가로 나는 위에 처럼 cnt=1 을 선언해주고 2를 제외해주고 제출을 했었는데,

 

 

이렇게 cnt=0 으로 해주고 2를 제외하는 조건을 삭제해주는게 더 깔끔한 코드같다.

 

 

 

여기까지 완료하면 이 시점까지 dp는 1과 2로만 만들수 있는 경우의 수들만 저장되어있다.

 

 

이후 3을 더한 경우의 숫자도 체크해보면

 

구하려는 인덱스의 -3 번째의 값을 더해주면 된다.

 

위 계산 이후 dp[3] 은 1+1+1, 2+1 까지만 계산 된 상태

 

dp[3] 에다가 dp[0] 의 값 1을 더해주면 dp[3]에서 3 이나오는 경우의 숫자까지 합해지는 셈이다.

 

 

이 과정으로 5를 구해볼때,

 

5-3 = 2

 

dp[5]+=dp[2]

 

dp[2] 의 값을 dp[5] 에다가 더해주면 값이 나온다.

 

 

왜냐하면,

 

dp[2]는  1+1, 2  2가지로 이루어져있다.

 

dp[5]는  1+1+1+1+1 , 2+1+1+1, 2+2+1 으로만 이루어져있는데, 

 

dp[5] 나머지 경우들을 더한다.  3+1+1, 3+2  <- 이 부분이 dp[2] 의 값의 갯수와 같다. 

 

 

 

 

이런식으로 쭉쭉 계산해 나가면 3을 더한 경우의 숫자들까지 모두 계산 되어 저장된다.

 

 

 

 

 

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

정답