Inor

[백준] 11015번 붕어빵 판매하기 본문

Algorithm/백준

[백준] 11015번 붕어빵 판매하기

Inor 2017. 11. 27. 13:32

- 문제 : https://www.acmicpc.net/problem/11052


 남은 붕어빵을 세트로 판매하는 문제입니다. 세트를 어떻게 나누어야지 이윤을 가장 많이 남길 수 있는지 풀어야됩니다. 이전 값이 다음 값에 영향을 줄 수 있기(memoization) 때문에 DP로 풀었습니다.




- 풀이



 먼저 하나의 경우를 만들고 각각을 분류하며 풀었습니다. 경우를 나열해본 결과 D[N]을 구하기 위해 D[N]부터 D[1]까지 적절하게 더해주며 결과를 도출했습니다. D[N]을 구하기 위해 먼저 N개의 붕어빵 세트를 만들었을때 값을 D[N]에 넣어줬습니다. 그리고 나머지 값들과 비교해줬습니다. D[N] < D[N-j] + D[N-(N-j)]로 비교하면 N보다 작은 값 중에 가장 큰 값과 가장 작은 값을 차례로 비교할 수 있었습니다. N이 6일 경우 6개 세트 가격을 D[6]에 넣고 (1,5), (2,4), (3,3), (4,2), (5,1)을 비교했습니다. 그러나 (1,5)와 (5,1)은 같은 값이기 때문에 경우의 수에서 반은 제외했습니다. D[i]의 i와 (x,y)에서 x+y는 항상 같은 값이 나와야하기 때문에 서로 대응되는 인자끼리 비교했습니다.




- 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class FishBread {
	int N;
	int[] cost;
	int[] D;

	void solve() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int half;

		N = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		cost = new int[N + 1];
		D = new int[N + 1];
		for (int i = 1; i < N + 1; i++) {
			cost[i] = Integer.parseInt(st.nextToken());
		}

		D[1] = cost[1];
		for (int i = 2; i < N + 1; i++) {
			half = i/2;
			D[i] =  cost[i];
			for (int j = 1; j <= half; j++) {
				if(D[i] < D[i - j] + D[i - (i - j)]){
					D[i] = D[i - j] + D[i - (i - j)];
				}
			}
		}
		
		System.out.println(D[N]);
	}

	public static void main(String[] args) throws IOException {
		FishBread m = new FishBread();
		m.solve();
	}

}


'Algorithm > 백준' 카테고리의 다른 글

[백준] 2851번 슈퍼 마리오  (0) 2017.12.18
[백준] 10250번 ACM 호텔  (0) 2017.12.10
[백준] 14888번 연산자 끼워넣기  (0) 2017.11.20
[백준] 14891번 톱니바퀴  (0) 2017.11.13
[백준] 5427번 불  (0) 2017.11.06
Comments