[Week of DP] BOJ 1309 #1

문제 : www.acmicpc.net/problem/1309

 

DP문제 중에서도 낮은 난이도의 문제라 선정해봤다.

 

n을 기준으로

사자를 0마리 넣을 경우(i=0), 경우의 수는 1

사자를 1마리 넣을 경우(i=1), 경우의 수는 n * 2

.

.

.

사자를 n마리 넣을 경우(i=n), 경우의 수는 2(지그재그로)

 

요렇게 공식이 나올 것 같은데.. 문제는 i가 2일 때부터이다.

n이 4일 경우에는 답으로 나와야 하는 수가 41이다.

i = 0, 1

i = 1, 8

i = 2,?

i = 3,?

i = 4, 2

 

41 - 11 = 30이므로 2와 3일 때의 합이 30이 될 것이다

일단 2부터 손으로 구해보면

5+5 = 10 첫째행 고정하면 두 번째행의 바로 밑에 거 제외하고 모든 게 될 수 있음. 첫째 행이 변동되므로 5+5

3+3 = 6 첫째행 제외하고 두 번째행부터 세면 3+3이 됨

1+1 = 2 첫째, 둘째 행 제외하고 세면 1+1이 됨

 

3을 손으로 구해보면

3+3 = 6 첫째, 둘째행 고정하면 3+3

2+2 = 4 둘째행 제외하면 2+2

1+1 = 2 첫째행 제외하면 1+1

 

여기까지는 어떻게든 구했는데.. 이걸로 점화식을 어찌 만들어야 될지 감이 안 온다.

약 한 시간쯤 머리를 싸매다가 일단은 내려놓고 해답을 찾아서 다음 포스팅에서는 풀이를 하려고 한다.