[백준(baekjoon) 11052] 붕어빵 판매하기

문제

백준 11052

n개의 붕어빵이 남았고, 이 중 i개로 이루어진 세트의 가격을 Pi라고 한다.
세트 메뉴의 가격이 주어졌을 때, 최대 수익을 구하는 프로그램을 작성하시오.

• 예시 n = 4;
• P1 = 1, P2 = 5, P3 = 6, P4 = 7;
• ANSWER : P2, P2 = 5 + 5 = 10;

해결

1, 2, 3의 더하기 문제와 흡사하다.
n을 이룰 수 있는 조합을 찾아 각각의 Pi를 모두 더한 값 중 최대 값을 찾는 문제이다.
다른 점은 조합이 1, 2, 3만으로 이루어지지 않는다는 것.

결론을 먼저 이야기 한다면,
두 원소의 합이 n이 되는 순서를 고려하지 않은 조합을 찾고, 각 max 가격을 찾아 더하면 된다.

1. ‘두 원소의 합’인 이유는 아래와 같다.
   
   • n의 max가격을 mn이라 하고 m = a + b일 때, mn = ma + mb이다.
2. 순서를 고려하지 않는 이유는 결국 우리가 찾는건 총 가격이기 때문이다.
   
   • 따라서, n/2..1으로 기준으로 찾는다.

문제 설명에 나와 있는 예시를 적용하자면 다음과 같이 나온다.

• n = 1 : {p1 = 1} => m1 = 1
• n = 2 : {p2 = 5}, {m1 + m1 = 2} => m2 = 5
• n = 3 : {p3 = 6}, {m2 + m1 = 6} => m3 = 6
• n = 4 : {p4 = 7}, {m3 + m1 = 7}, {m2 + m2 = 10} => m4 = 10

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

공통적인 것

• max, price

1. Top-Down 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[] max;
5.    static int[] price;
6.
7.    public static void main(String[] args) {
8.        Scanner sc = new Scanner(System.in);
9.        int n = sc.nextInt();
10.
11.        price = new int[n + 1];
12.        max = new int[n + 1];
13.
14.        for (int i = 1; i <= n; i++) {
15.            price[i] = sc.nextInt();
16.            max[i] = price[i];
17.            for (int j = i - 1; j >= i / 2 && i > 1; j--) {
18.                if (max[j] + price[i - j] > max[i]) max[i] = max[j] + price[i - j];
19.            }
20.        }
21.
22.        System.out.println(max[n]);
23.    }
24.
25.    public static int goTo (int n) {
26.        if (max[n] == 0) {
27.            max[n] = price[n];
28.            if (n > 1) {
29.                for (int j = n - 1; j >= n / 2; j--) {
30.                    if (goTo(j) + goTo(n - j) > max[n]) max[n] = max[j] + max[n - j];
31.                }
32.            }
33.        }
34.        return max[n];
35.    }
36.}

2. Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[] max;
5.    static int[] price;
6.
7.    public static void main(String[] args) {
8.        Scanner sc = new Scanner(System.in);
9.        int n = sc.nextInt();
10.
11.        price = new int[n + 1];
12.        max = new int[n + 1];
13.        max[1] = price[1];
14.
15.        for (int i = 1; i <= n; i++) {
16.            price[i] = sc.nextInt();
17.            max[i] = price[i];
18.            for (int j = i - 1; j >= i / 2 && i > 1; j--) {
19.                if (max[j] + max[i - j] > max[i]) max[i] = max[j] + max[i - j];
20.            }
21.        }
22.
23.        System.out.println(max[n]);
24.    }
25.}

결과

1. Bottom-Up 방식
2. Top-Down 방식