BOJ 11052 붕어빵 판매하기

문제출처 : https://www.acmicpc.net/problem/11052

1. 문제요약

- 붕어 빵을 N개 팔아서 남는 최대 수익?

- 붕어빵을 i개 씩 묶어서 판매하는 가격은 Pi

- 붕어빵이 4개 남아있고, 1개 팔때 2 / 2개 팔때 5, 3개 팔때 6 / 4개 팔때 7인 경우

  붕어빵을 2개 2개 씩 팔면 10이 최대 수익

- 1 <= N <= 1,000

- 1 <= Pi <= 10,000

2. 접근방법

- 최대값은 최대값에서 찾는다.

- N 번째 붕어빵을 판매했을 때 최대 수익을 d[n]이라 하면

- N 번째 최대 수익은 이전까지 최대 수익(d[0] ~ d[n-1]) 중에 남은 붕어빵을 세트로 판매한 가격의 합의 최대

- 위의 예시를 따르자면

  d[1] = P1

  d[2] = 1 + 1 or 2 = d[1] + P1 or d[0] + P2

  d[3] = 1 + 1 + 1 or 1 + 2(2 + 1) or 3 = d[1] + P2(1 + 2) or d[2] + P1(1 + 1과 2 중의 큰값 + 1) or d[0] + P3(3)

  d[4] = 1 + 1 + 1 + 1 or 1 + 2 + 1(2 + 1 + 1, 1 + 1 + 2) or 1 + 3(3 + 1) or 4 = d[1] + P3 or d[2] + P2 or d[3] + P1 or d[0] + P4

- 즉, d[n] = max(d[0] + Pn, d[1] + Pn-1, d[2] + Pn-2, ... , d[n-1] + P1)

3. 시간복잡도

- 2 + 3 + ... + n = n(n+1)/2 = 약 500,000

4. 회고

- 생각해보면 굳이 d 배열을 쓸 필요없이 p 배열 하나면 되는 거였네

소스코드

#include<iostream>
using namespace std;

int n, p[1001], d[1001];

int main(void){
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> p[i];
	d[1] = p[1];
	for(int i = 2; i <= n; i++){
		for(int j = 0; j < i; j++)
			d[i] = max(d[i], d[j] + p[i - j]);
	}
	cout << d[n] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]