티스토리 뷰
Codeforces : Ordering Pizza
난이도 : 6/10 (탐색은 탐색이였는데 해 탐색인줄 몰랐음 ㅅㄱ)
문제보기
http://codeforces.com/problemset/problem/865/B
코딩대회가 시작했고, 참가자를 위해 피자를 주문하려고한다. (ㅇㅅㅇ!! 착한 대회인정) 피자는 2종류밖에 없다. (그래도 압도적인 감사 ㅠ.ㅠ) 그리고 모든 피자는 정확히 S 조각으로 이루어져있다.
i 번째 참가자는 정확히 S[i] 조각을 먹을 것이고, 그리고 타입 1의 피자 "한조" 각당 a[i] 만큼의 기쁨이 상승하고 타입 2의 피자 "한조" 각당 b[i] 만큼의 기쁨이 상승한다고 알려져있다.
1타입과 2타입 피자는 어떤 갯수로도 주문 가능하지만, 모든 참가자들이 만족할 만큼의 피자를 먹을 수 있는 최소한의 피자를 주문하려고 한다. 이 경우 성취할 수 있는 최대 행복도는 몇인가?
Input
Output
힌트
문제 해설
문제의 조건은 다음과 같다
ㅇ 모든 참가자드른 S[i] 만큼의 피자 조각을 먹고싶어해욨!
ㅇ 근데 피자는 최소로 사고싶어욨!
ㅇ 하지만 또 행복도는 최대가 되야해욨!
필자는 이런 해찾기 문제를 산업공학과 전공 경영과학을 들으면서 많이 접했던것 같다. 근데 코딩문제로는 처음 접했다. ... 어렵다... 사실 경영과학에서 배운 내용이 맞는지도 헷갈린다.
= 7*7 + 5*8 + 12*8 +6*11 + 3*7 + 4*9 + 1*6(Type 1 다떨어져서 2로떼움) + 2*8(떨이두조각)
<하지만 애매한 조건때문에 후보군이 생긴다. 확실히 Type A 할당은 6조각 필요한 녀석과
5조각 필요한 녀석이다. 그리고 Type B 할당은 확실히 12조각 필요한 녀석이다.
그러면 3명이 남는다. 7조각 필요한 녀석과 5조각 필요한녀석, 3조각 필요한 녀석.
어디로 할당시켜줘야하나?>
후보군을 상대로 일일히 다 완전탐색 해줘야하나? 기발한 생각이 없을까 곰곰히 생각하면서 다른 유저들의 답을 보았지만 별다른 해결책이 떠오르지 않았다.
< (7, 4, 7), (12, 5, 8), (3, 3, 7) 은 Type A 보다 Type B의 행복도가 더 크다. 반면에 (5, 8, 8), (6, 11, 6), (5, 9, 6) 은 Type A의 행복도가 더 크다.>
그러다 문득 피자 분류를 해버렸다.
1 우선적으로 Type A에는 Type A의 행복도가 Type B의 행복도보다 큰 녀석들을 배치한다. 그리고 Type B에는 Type B의 행복도가 Type A의 행복도보다 큰녀석들을 분류한다.
2 위 경우에서는 Type B를 기준으로, B 의 행복도가 더 큰 녀석들이 딱 맞는지 확인해보자. 7+12+3 은 20보다 크다. 따라서, 2만큼 차감을 해줘야하는데 어디서 차감을 해줘야하나?
나는 (7, 4, 7) 녀석을 2만큼 뺴줬다. 왜냐하면 (3, 3, 7) 녀석은 B를 포기하면서 행복도 7을 못얻고 A를 취하면서 행복을 고작 3 얻기 때문이다. 반면에 (7, 4, 7)은 7을 못 얻고 A를 취하면서 4를 얻을 수 있다.
즉 (완성될 행복도 -7)+4 냐 (완성될 행복도 -7) +3 이냐의 문제다. 당연히 전자가 클것이다. 그런데 (12, 5 , 8) 은 어떨까? 놀랍게도 Type B 갯수를 맞추기위해 (12, 5, 8)을 두 개 포기하는 것과 (7, 4, 7)을 두개 포기하는 것으 같다.
그래프를 그려보고 싶지만, 도저히 명확하게 그릴 능력이 생기지 않았다.
위는 Type A 와 Type B 수 가 결정되어 있을 때 행복도가 가장 큰 선택을 하는 것이다. 하지만 가장 행복도가 가장 큰 선택을 하고 가장 큰 행복도만 출력하면된다. 가장 큰 행복도만 출력하면 되니까
1
A 행복도가 큰 놈은 Type A 행복도로, Type B 행복도가 큰 놈은 Type B 행복도로.
2
둘 중 Slice 조각으로 안나뉘는 것은 다른 Type 으로 변환한다.
3
아마 둘다 넘을테다. 예로 Slice 조각이 10이고, (Type A 갯수, Type B 갯수) (46, 14) 이렇게 떨어지면... Type A의 행복도 절대값 차가 작은놈을 B로 변환한것 (40, 20) 과 Type B의 행복도 절대값 차가 작은놈을 A로 변환한것 (50, 10) 과 비교하면 될까?
될것같다! 해보자!!.
설계는 했는데 예외처리 때문에 쪼금 힘들었었다.
그리고 문제를 풀다보니 왜 문제 분류가 정렬과 탐색으로 되어있는지 이해가 갔다.
ternary search 라는 해탐색 알고리즘에 대해서 공부는 따로 또 해봐야할 거같다.
소스보기
'알고리즘 문제 > sort, search' 카테고리의 다른 글
Leetcode - 1. Two Sum (0) | 2022.07.21 |
---|---|
codeforces 283 div2 d tennis game (0) | 2019.11.02 |
CF 1041D Glider (0) | 2018.09.20 |
888E : Maximum Subsequence (0) | 2017.11.12 |
- Total
- Today
- Yesterday
- Arena
- grafana cloud
- arena simulation
- Discrete Mathematics
- paul wilton
- 대규모 시스템 설계 기초
- Trie
- 백준
- 시뮬레이션
- 아레나 시뮬레이션
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- beginning javascript
- 이산 수학
- 아레나
- 자바스크립트 예제
- 조합 코딩
- 최단경로 알고리즘
- javascript
- flutter
- rosen
- 데이터 중심 애플리케이션 설계
- 자바스크립트
- 아레나시뮬레이션
- 로젠
- Simulation
- Propositional and Predicate Logic
- 명제논리
- 이산수학
- 그라파나
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |