Inor
[백준] 11015번 붕어빵 판매하기 본문
- 문제 : 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