-
Codeforces : Ordering Pizza알고리즘 문제/sort, search 2017. 10. 2. 16:39반응형
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
첫 번째 라인에는 N과 S가 주어진다. (1<=N<=10^5, 1<=S<=10^5). N은 참가자 수이고, S는 피자가 나뉠수 있는 조각 수이다.그다음 주어지는 N 줄은 S[i], a[i], b[i] 이다. ( 1<=S[i]<=10^5, 1<=a[i]<=10^5, 1<=b[i]<=10^5). S[i]는 i번째 참가자가 참가자가 먹어야할 피자 조각 수이며, a[i]는 i번째 참가자가 1타입 피자 먹었을 때 얻을 수 있는 행복이며, b[i]는 2타입 피자를 먹었을 때의 경우이다.Output
도달할 수 있는 최대 행복도를 출력한다.힌트
input 1 인경우 3명의 참가자 피자는 12조각 조각내기 가능이다. 피자 1개로도 충분히 3명을 만족시킬수 있다. 그것은 각각 3조각 4조각 5조각 주는것이다. 그럼 3*5+4*6+5*9와 3*7 + 4*7 + 5*5를 비교하고 피자 타입을 결정하면된다. 15+24+45=84 vs 21+28+25=74 이므로 1타입 피자를 한개 시키면된다.input 2인 경우 6명의 참가자 피자는 10조각 조각내기 가능이다. 그럼 38조각이 필요하므로 최소 피자는 4개가 필요하다. 이 경우 5 가지의 경우가 생긴다. (Type A, Type B) = {(0, 4), (1,3), (2,2), (3,1) ,(4,0)} 이 때의 최대값은 (1,3) 일 때의 7*7 + 5*8 + 12*8 +6*11 + 3*7 + 4*9 + 1*6 = 314 이다.문제 해설
문제의 조건은 다음과 같다
ㅇ 모든 참가자드른 S[i] 만큼의 피자 조각을 먹고싶어해욨!
ㅇ 근데 피자는 최소로 사고싶어욨!
ㅇ 하지만 또 행복도는 최대가 되야해욨!필자는 이런 해찾기 문제를 산업공학과 전공 경영과학을 들으면서 많이 접했던것 같다. 근데 코딩문제로는 처음 접했다. ... 어렵다... 사실 경영과학에서 배운 내용이 맞는지도 헷갈린다.
우선 input 2를 살펴보자.1. Type 1 피자 0개 Type 2 피자 4개-> 7*7 + 5*8 + 12*8 + 6*6 + 3*7 + 5* 6 그리고 떨이 두조각은 행복도가 젤 큰놈한테 준다. +2*8.= 288= 272 ( 떨이 두조각 제외)2. Type 1 피자 1개 Type 2 피자 3개-> 타입 1의 행복도가 젤 큰놈한테 1타입을 우선 몰아준다. 남은 조각은 그다음 녀석에게 몰아준다.
= 7*7 + 5*8 + 12*8 +6*11 + 3*7 + 4*9 + 1*6(Type 1 다떨어져서 2로떼움) + 2*8(떨이두조각)= 330 ?? 엥...? 문제 아웃풋이랑 다르잖아..?이제보니 참가자들은 정확하게 S[i] 만큼의 갯수를 먹으니까... 떨이 2조각이 필요없는거다.떨이 2조각 을 제외하니까= 314이다.3. Type 1 피자 2개 Type 2 피자 2개-> 타입 1의 행복도가 타입 2의 행복도보다 높은녀석에게 타입 1을 우선할당한다. 그리고 타입 2의 행복도가 타입 1의 행복도보다 높은 녀석을 타입 2를 우선 할당한다. 아래는 일단 해본그림이다.<하지만 애매한 조건때문에 후보군이 생긴다. 확실히 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' 카테고리의 다른 글
codeforces 283 div2 d tennis game (0) 2019.11.02 CF 1041D Glider (0) 2018.09.20 888E : Maximum Subsequence (0) 2017.11.12 Codeforces : Ordering Pizza (0) 2017.10.02
