ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 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

    댓글 0

Designed by Tistory.