[Algorithm] 백준 110502 BackJoon 붕어빵 판매하기

BackJoon 

# 110502 - 붕어빵 판매하기

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

우선 DP를 적용해 보겠다. 만약 4개의 붕어빵을 파는 경우 각각 1개를 팔 경우, 2개를 팔 경우, 3개를 팔 경우, 4개를 팔 경우 최대 이익을 구해야한다. 

판매 붕어빵 갯수	이익
1개	1원
2개	5원
3개	6원
4개	7원

위와 같이 붕어빵의 갯수에 따라 이익이 다를 경우, 만약 붕어빵을 4개 팔 경우 최대 이익이 얼마일 것인가??

차근차근 생각해보자. 붕어빵 4개를 판매하는 경우는 총 몇가지 일까?

1개 3개 = 7원

2개 2개 = 10원

3개 1개 = 7원

4개 0개 = 7원

총 3가지 방법이 있을 것이다. 하지만 2개2개를 파는 것이 가장 큰 이익을 취한다. 즉 답은 10원이 될 것이다. 

이제 문제 파악은 끝났다. 

자 이를 DP방법으로 접근해보자.

아까 판매 붕어빵의 갯수에 따라 발생되는 이익을 int P[] = new int[N+1]; 라는 배열에 담아 두겠다.

만약 N개의 붕어빵을 팔아야 한다면, 최대이익은 무엇이다. 라는 식을 

우리는 D[N]의 값이라 표현하겠다. 즉 D[N] 안에 들어있는 값은 붕어빵 N개를 판매할 경우 최대 이익이다.

그 다음 생각 해볼 것이 마지막 손님에게 붕어빵을 몇개를 판매할 수 있을까 라는 경우이다.

아마 1 ~ N개가 있을 것이다. 

즉, N이 4개 일 경우(붕어빵을 4개 판매해야하는 경우)

만약 마지막 사람에게 붕어빵 1개를 팔았다면, 마지막 손님이 오기 전에 판 붕어빵의 갯수는 4-1 인 3개일 것이다. 만약 마지막 손님에게 붕어빵 2개를 팔았다면, 마지막 손님이 오기 전에 판 붕어빵의 갯수는 4-2 인 2개가 될 것이다. 이 원리를 점화식으로 옴겨보자.

마지막 손님에게 1개 판매하는 경우

D[N] = D[N-1] + P[1];

마지막 손님에게 2개 판매하는 경우

D[N] = D[N-2] + P[2];

마지막 손님에게 i개 판매하는 경우

D[N] = D[N-i] + P[i];

.......

마지막 손님에게 N개 판매하는 경우

D[N] = D[N-N] + P[N];

이제 원리를 적용하면 아래 4가지로 생각해볼 수 있다.

D[4] = 붕어빵을 마지막사람에게 0개 판매하는 이익 + 일전에 붕어빵 4개를 판매한 최대 이익

D[4] = 붕어빵을 마지막사람에게 1개 판매하는 이익 + 일전에 붕어빵 3개를 판매한 최대 이익

D[4] = 붕어빵을 마지막사람에게 2개 판매하는 이익 + 일전에 붕어빵 2개를 판매한 최대 이익

D[4] = 붕어빵을 마지막사람에게 3개 판매하는 이익 + 일전에 붕어빵 1개를 판매한 최대 이익

하지만 가장 큰 이익을 D배열에 갱신해야 하기 때문에 각 경우에 따라 이익이 구해질 때마다 일전에 저장된 값과 계속적으로 비교해서 최고의 이익으로 갱신 해야 한다. 또 우선 붕어빵 0개를 파는 경우의 최대 이익은 0원이기 때문에 D[0] = 0 으로 초기화 해줘야 한다. 따라서 위 내용을 종합적으로 구성하면 아래와 같은 코드가 나온다. 

public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(); //판매할 붕어빵의 갯수
		
		int d[] = new int[n+1]; 
		int p[] = new int[n+1]; 
		
		for(int i=1; i<=n;i++) p[i] = sc.nextInt(); //갯수당 붕어빵 이익

		d[0] = 0;
		for(int i=1; i <= n; i++){
			for(int j=1; j<=i; j++){
				d[i] = Math.max(d[i],p[j]+d[i-j]);
			}
		}
		System.out.println(d[n]);
		
		
	}