백준 10844, 2156
1) 백준 10844 (쉬운계단수 : https://www.acmicpc.net/problem/10844)
하나도 안쉬운 계단수 ㄹㅇ;;;;;;
어떻게 이런 생각을 하지;;;
아무 생각없이 앞자리 순서대로 써놓고 생각해도 생각해도 안나오는데
뒷자리를 고정시킬 생각을 하다니;;
뒷자리가 i 이면 그 다음 올 수 있는 숫자는 i-1, i+1일 수밖에 없다.(i = 1 ~ 8인 경우)
그리고 뒷자리가 i로 끝나는 경우에 가능한 계단수를 미리 계산해놓으면 이를 가져와 쓰기만 하면 된다.
간단히 변수 설명을 하자면 DP는 쉬운계단수가 저장된 배열이다.
DP[N][K]에서 N은 몇 자리수인지를 의미한다. (1은 한자리 수/ 2는 두자리 수/ 3은 세자리 수 ...)
K는 뒤에 오는 수이다. (K=1이면 뒤가 1로 끝나는 수인 것.)
예를들어 DP[2][4] 를 해석하면 두 자리수중, 맨 뒷자리가 4로 끝나는 수의 쉬운계단수 인 것이다.
(구체적으로 보면 34, 54 이렇게 2개가 되겠다 :
한 자리수 중 3으로 끝나는 계단수 + 4를 이어붙이기
한 자리수 중 5로 끝나는 계단수 + 4를 이어붙이기 한 결과이다.)
문제 예시부터 보면
n = 1이면 모두가 계단 수 이므로 모두 1을 할당해준다.
이후의 계산에서는
DP[n][k] = DP[n-1][k-1] + DP[n-1][k+1]을 통해 계산해준다.
(위에서 말했던 것대로 k=1~8까지는 이것이 적용된다).
k = 0이나 9인 경우에는 뒷자리에 1, 8이 오는 경우 1개밖에 참고할 수 없으므로 알맞게 조건을 걸어준다.
따라서
n | k 0 1 2 3 4 5 6 7 8 9
1 - - 0 1 1 1 1 1 1 1 1 1
2 - - 1 1 2 2 2 2 2 2 2 1
3 - - 1 3 3 4 4 4 4 4 3 2
...
가 된다. ㄹㅇ 안어려운 계단수
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/5_10844.cpp
2) 백준 2156 포도주 시식 : https://www.acmicpc.net/problem/2156
문제보자마자 day4 DP에 풀었던 계단문제랑 아주아주아주 유사하다는 것을 알 수 있었다.ㅎㅎ
개꿀 하면서 풀다가 틀렸다.
보니까 이건 마지막 잔을 안 마실 수도 있기 때문이다.
그래서 마지막에 안마시는 경우 max값을 출력했다.
틀렸다.
DP값을 안 마실 때 그에 맞게 갱신을 해줘야 한다.
만약 안마실때는 DP를 이전 값으로 갱신해줘야 한다.
그래서 DP[n] 출력하면 끝
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/5_2156.cpp
끗
