[BOJ] 11052번 붕어빵만들기(다이나믹프로그래밍)

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

[ 문제 요약 ] 

- 입력으로 총 붕어빵 개수가 주어지고, 각각의 개수마다 가격이 주어집니다.

- 주어진 입력을 기준으로 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하는 문제입니다.

[ 풀이 과정 ] 

- 다이나믹 프로그래밍의 해결 과정을 잘 아시는 분이라면 쉬운 문제였다고 생각합니다. 다이나믹 프로그래밍의 원리는 작은 문제를 해결하여 더 큰 문제를 해결해나가는 과정입니다.

- 간략하게 풀이과정을 말하자면, 각 수의 최대 값을 구하여 새로운 배열에 저장하였습니다. 또 그 각 수의 최대값을 이용하여 더욱 큰 수의 최대값을 구하는 방식으로 해결하였습니다. ( 구해 놓은 답을 이용하여 다음 수를 해결하는 방식입니다.)

[ 소스 코드 ]

- s[10000] 배열은 각 수의 최대값을 저장하는 배열이고, p[10000]는 입력된 수를 저장하는 배열입니다.

- 예를 들어, 3의 최대값은 p[1] + p[1] + p[1] , p[1] + p[2], p[3] 중 최대값이 답이 됩니다. j가 1부터 j가 i/2되는 순간까지(i/2까지 구하는 이유는 i/2이상이 되면 1+2, 2+1처럼 같은 경우를 반복하기 때문입니다.) s배열을 이용하여 최대값을 구합니다. (s 배열을 이용하면 p[1] + p[1] + p[1] , p[1] + p[2] 를 s[1] + s[2]로 구할 수 있다. s[2]는 p[1] + p[1] + p[1] , p[1] + p[2] 두 경우의 최대값이기 때문입니다.