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

풀이 1) 이차원 배열

1. d[i][j]

   • 1~i 번째 포도주까지 마셨을 때, 마실 수 있는 포도주의 최대 양
     
     i번째 포두주 잔은 j 번 연속 마신 포도주 잔임

2. a[i]

   • (i : 1~n)
   • i 번째 포도주의 양

3. 결과

   • d[n][0] = max( d[n-1][0] , d[n-1][1], d[n-1][2] )
   • d[n][1] = d[n-1][0] + a[n]
   • d[n][2] = d[n-1][1] + a[n]

풀이 2) 일차원 배열

1. d[i]

   • 1~i 번째 포도주까지 마셨을 때, 마실 수 있는 포도주의 최대 양

2. a[i]

   • (i : 1~n)
   • i 번째 포도주의 양

3. 결과

   • 0번 연속 : d[i] = d[i-1]
   • 1번 연속 : d[i] = d[i-2] + a[i]
   • 2번 연속 : d[i] = d[i-3] + a[i-1] + a[i]

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

풀이

1. s : n열의 상태

   • [0] [1] [2]
   • X O X
   • X X O

2. d[n][s]

   • 2 x n 에서 얻을 수 있는 최대 점수. n열에서 뜯은 스티커는 s

3. a[i][j]

   • i열 j행에 들어있는 스티커의 점수

4. 결과

   • d[n][0] = max( d[n-1][0] , d[n-1][1] , d[n-1][2] )
   • d[n][1] = max( d[n-1][0] , d[n-1][2] ) + a[n][1]
   • d[n][2] = max( d[n-1][0] , d[n-1][1] ) + a[n][2]

5. 정답

   • max( d[n][0], d[n][1], d[n][2] )

==> 어렵다. 다시 풀어야함

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

풀이 1)

1. d[n][l]
   • 자리가 n & 끝자리가 l 인 이친수의 개수
2. d[n][0]
   • d[n-1][0] + d[n-1][1]
3. d[n][1]
   • d[n-1][0]
4. ans
   • d[n][0]+d[n][1]

=> 근데 왜 답은 틀렸다고 나올까..?

풀이 2)

1. d[n]
   • n 자리 이친수의 개수
   • d[n-1] + d[n-2]

=> 이 방법도 틀리게 나옴

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

풀이

1. 이차원 배열로 생각

2. 식 세우기 … 다음과 같이 시도했지만 정답 도출 실패..
   ==> 답지 보고 다시 풀 예정

1
2

int d[n][l] : 자리수가 n 자리인 수의 마지막 수가 l인 오르막 수의 개수
d[n][l] = d[n-1][l] + (10-l)  ( l은 0~9 )

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

틀린 풀이

직접

길이가 1인 계단수

길이가 2인 계단수

…

를 하나하나 구해보니

길이가 n인 계단 수 = 길이가 n-1인 계단수 * 2 -1 이라는 규칙이 나왔다.

하지만 계속 채점 결과는 틀렸다고 나옴..

맞는 풀이

이차원 배열로 품

* D[i][j] : 길이 i, 마지막 숫자가 j인 계단 수의 개수
* D[N][L] : N자리 계단수 마지막수는 L인 계단수의 개수
* D[N][L] = D[N-1][L-1] + D[N-1][L+1] (L : 1~8)
* D[N][0] = D[N][1]
* D[N][9] = D[N-1][8]