EddIT

문제

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

풀이

2차원 배열로 메모이제이션해야 되는 문제였다.

D[N][L]을 N자리수에서 끝자리가 L로 끝나는 수의 계단수의 가지수라고 한다면

N자리 수에서 끝자리가 2로 정해지면, D[N-1][1]과 D[N-1][3]을 구하면 된다.

이를 점화식으로 표현하면

D[N][L] = D[N-1][L-1] + D[N-1][L+1]

문제

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

풀이

D[i]이 i개를 팔 때 얻을 수 있는 최대 수익

P[i]는 i개를 팔 때 얻는 수익

총 붕어빵이 i개 있을 때

1개를 팔았을 때 최대값은 P[1] + D[i-1]

2개를 팔았을 때 최대값은 P[2] + D[i-2]

j개를 팔았을 때 최대값은 P[j] + D[i-j]

이렇게 따져서 이들 값중에서 최대값이 D[i]

점화식을 살펴보면

D[i] = max(P[j] + P[i-j])

단, j의 범위는 1<= j <= i

이를 바탕으로 코딩을 해보면 된다.

#아직 프로그래밍적 사고와 다이나믹 프로그래밍적 문제 접근 방식이 익숙하지 않은것 같다.

문제

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

풀이

다이나믹 프로그래밍으로 풀 수 있었다.

n일때 1,2,3을 더해서 n을 표현하는 방법의 가지수를 d[n]이라고 한다.

마지막에 올 수 있는 숫자는 1, 2, 3 인데 

1이 오면 d[n-1]

2가 오면 d[n-2]

3이 오면 d[n-3] 이 성립된다.

이를 바탕으로 점화식을 세워보면

d[n] = d[n-1] + d[n-2] + d[n-3]

top-down 방식

bottom-up 방식

문제

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

풀이

피보나치 수열과 같다.

bottom-up 방식으로 푸니까 런타임에러가 뜬다.

그래서 top-down방식으로 풀어봄

문제

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

풀이