SHARE
TWEET

Untitled

a guest Feb 19th, 2019 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. //  CDJ_ Ratatouille.cpp
  3. //  algorithm
  4. //
  5. //  Created by hubring on 2019. 2. 16..
  6. //  Copyright © 2019년 hubring. All rights reserved.
  7. //
  8.  
  9. #include <stdio.h>
  10. #include <iostream>
  11. #include <algorithm>
  12.  
  13. using namespace std;
  14.  
  15.  
  16. int N, P;
  17. int pack[51][51];
  18. int ingredient[51];
  19. int startIdx[51];
  20.  
  21. float usePack(int ing, int pack, int quot){
  22.     int remain = pack - (ing*quot);
  23.     float per = (remain*100)/(float)(ing*quot);
  24.    
  25.     return per;
  26. }
  27.  
  28.  
  29.  
  30. int getMaxPackage(){
  31.     int res = 0, quot = 1;
  32.  
  33.     //몫(quot)을 1부터 시작하여 만들 수 있는 요리의 개수를 구한다.
  34.     //몫의 최대 크기는 (최대 성분 * 몫 * 110%) <= (최대 성분의 패키지 종량)을 넘지 않는다.
  35.     while(true){
  36.         int cnt = 0;
  37.        
  38.         for(int i=0; i<N; i++){
  39.             int inRangeIdx = -1;
  40.          
  41.             for(int j =startIdx[i]; j<P; j++){
  42.              
  43.                 // i번째 성분을 quet개 만들때 최소 90% 범위 내 패키지 종량을 찾는다.
  44.                 if(usePack(ingredient[i], pack[i][j],quot)>=-10){
  45.                     inRangeIdx = j;
  46.                     break;
  47.                 }
  48.                
  49.             }
  50.          
  51.             //최소 90퍼 범위 내에 패키지 종량이 없다면 더이상 요리를 만들 수 없으므로 결과를 리턴한다.
  52.             if(inRangeIdx==-1) return res;
  53.            
  54.             //사용가능한 inRangeIdx를 시작지점으로 설정한다.
  55.             startIdx[i] = inRangeIdx;
  56.          
  57.             //해당 110% 범위 내에 패키지 종량이 있다면 해당 패키지로 quet개의 요리를 할 수 있으므로 cnt를 증가시킨다.
  58.             if(usePack(ingredient[i], pack[i][inRangeIdx],quot)<=10){
  59.                 cnt++;
  60.             }
  61.         }
  62.        
  63.         //요리 quet개 만들때 필요 성분 N개를 모두 만족하므로 결과 횟수를 증가시킨다.
  64.         if(cnt == N){
  65.             res++;
  66.          
  67.             //해당 startIdx[i]번쩨에 있는 패키지는 사용했으므로 다음번째로 시작할 수 있도록 설정한다.
  68.             for(int i =0; i<N; i++){
  69.                 startIdx[i]++;
  70.             }
  71.         }else{
  72.        
  73.             quot++;
  74.         }
  75.     }
  76.  
  77.     return  res;
  78. }
  79.  
  80.  
  81.  
  82. void solve(int testNum){
  83.    
  84.     scanf("%d %d", &N, &P);
  85.  
  86.     for(int i=0; i<N; i++){
  87.         scanf("%d", &ingredient[i]);
  88.         startIdx[i] =0;
  89.     }
  90.    
  91.     for(int i=0; i<N; i++){
  92.         for(int j =0; j<P; j++){
  93.             scanf("%d", &pack[i][j]);
  94.         }
  95.         // package를 오름차순으로 정렬한다.
  96.         sort(pack[i], pack[i]+P);
  97.     }
  98.    
  99.     printf("Case #%d: %d\n", testNum, getMaxPackage());
  100.    
  101. }
  102.  
  103.  
  104.  
  105. int main(){
  106.    
  107.     int testCase;
  108.     scanf("%d", &testCase);
  109.    
  110.     for(int i=0 ;i<testCase; i++){
  111.         solve(i+1);
  112.     }
  113.    
  114. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top