맛있는감귤

문제 : https://www.acmicpc.net/problem/2579첫 번째 계단부터 최대점수를 구하고... 두 번째 계단의 최대점수 구하고.......마지막 계단의 최대 점수를 구하는 DP문제입니다.첫번째 계단을 밟았을 때 최대값은 첫번째 계단을 밟았을 때 받게 되는 점수가 됩니다. sum[1] = step[1]두번째 계단을 밟았을 때 최대값은 첫번째 계단을 밟고 두번째 계단을 밟았을 때 혹은 첫번째 계단을 밟지않고 2단 점프를 했을 때가 됩니다.세번째 계단 또한 두번째 계단을 밟았을 때 혹은 첫번째 계단을 밟고 세번째계단으로 2단점프를 했을 때가 됩니다.N번째 계단은 N-3번째 계단에서 N-1번째 계단까지 2단점프를 한 후, N번째 계단으로 점프를 했을 때 혹은 N-2번째 계단에서 2단점프를 했..

문제 : https://www.acmicpc.net/problem/11052 기초 DP문제입니다. 여느 DP 문제가 그렇듯이 가장 작은 수부터 고려해 점차 큰 수일 때 경우를 고려하는 Bottom-Up 방식으로 풀면됩니다. DP에서 가장 중요한 것은 메모이제이션 그리고 점화식이죠. 예를 들어, 첫 번째 테스트 입력을 보겠습니다.4 1 5 6 7먼저 붕어빵 개수 당 가격을 담고 있는 fish[4] 배열과 각 수의 팔았을 때 가장 큰 값을 가진 배열 sum[4]가 있다고 봅시다. 먼저 붕어빵 한개를 팔때 가장 비싸게 파는 sum[1] = fish[1]가 되겠죠. 그 다음 붕어빵 두개를 팔 때는 두개에 파는 가격 fish[2]와 한 개 값으로 두 개를 파는 경우(sum[1]+fish[1])가 나옵니다. 이 중..