26개의 댓글이 있습니다.

• 
  VOCList

  다음 줄에는 m 개의 문자열로 각 친구의 이름이 주어집니다.
  m과 n이 바뀐 것 같습니다

  
  12년 전 link

• 
  JongMan

  지적 감사요~

  
  12년 전 link

• 
  ggabu420

  아무도 못 먹는 음식도 나올 수 있다는 얘기가 되나요?

  
  11년 전 link

• 
  xcrossx

  입력에 '모든 친구는 하나 이상의 음식을 먹을 수 있다고 가정해도 좋습니다.' 써있는걸 보니 못먹는 케이스는 없는거 아닐까요?

  
  11년 전 link

• 
  ggabu420

  친구 한명이 최소 하나 이상의 음식을 먹는 것이라서,
  반대로 생각하면 가령 친구 4명이 모두 갈비찜밖에 못먹는다면
  다른 음식들은 아무도 못먹지만 친구 한명당 최소 하나 이상의
  음식을 먹을 수 있다는 조건에는 만족하니까요..

  
  11년 전 link

• 
  Signin

  반드시 모두 음식을 먹을 수 있는 경우가 생긴다고 가정해도 되나요~?

  
  11년 전 link

• 
  JongMan

  "모든 친구는 하나 이상의 음식을 먹을 수 있다고 가정해도 좋습니다."

  
  11년 전 link

• 
  Signin

  아..거기에서 그런 결론을 낼 수 있군요 ㅠㅠ
  감사합니다~!

  
  11년 전 link

• 
  kksuhj

  난 왜 런타임 오류가 나지... 아놔;

  
  11년 전 link

• 
  kksuhj

  책의 이름과 음식 수 범위랑 알고스팟의 그 범위가 다르네요

  
  11년 전 link

• 
  rlatkddn212

  ㄴ감사합니다 20으로 초기화 해서 계속 런타임 오류 떳었네요..

  
  10년 전 link

• 
  paradise7

  런타임 오류가 계속 뜨네요. ㅠㅠ.

  운영자님께서 확인해주실 수 있는지 모르겠네요.

  아니면 C++ 로 포팅 해보아야 겠습니다.

  https://algospot.com/judge/submission/detail/246365

  
  10년 전 link

• 
  Being

  질문은 질문과 답변 게시판에 해 주세요.

  
  10년 전 link

• 
  김영태

  계속 오답 처리가 나오는데요, 혹시 점검 테스트 케이스를 받아 볼수 있을까요??

  문제는 없어 보이는데, 그냥 오답이 되니 답답하네요. ㅠㅠ
  (kty027@nate.com 입니다)
  ※ 그리고 운영진이시니 제가 제출한 답안은 보실수는 있느신거죠?

  
  9년 전 link

• 
  Kureyo

  1. 데이타는 드릴 수 없습니다
  2. 자신의 생각과 코드를 포함한 질문글을 질문 게시판에 작성해서 다른 회원분들과 의견을 나누는 것이 좋을듯 합니다

  
  9년 전 link

• 
  na982

  #include
  #include
  #include
  #include
  #include
  using namespace std;

  int n, m;
  vector canEat[50], eaters[50];
  int best;

  void search(vector& edible, int chosen){
  if(chosen >= best) return ;

  int first = -1, t_size = 50;
  for(int i = 0; i < n; ++i){
      if(edible[i] == 0){
          if(t_size > canEat[i].size()){
              t_size = canEat[i].size();
              first = i;
          }
      }
  }
  if(first == -1){
      //best = min(best, chosen);
      best = chosen;
      return ;
  }
  
  for(int i = 0; i < canEat[first].size(); ++i){
      int food = canEat[first][i];
      for(int j = 0; j < eaters[food].size(); ++j){
          edible[eaters[food][j]]++;
      }
      search(edible, chosen+1);
      for(int j = 0; j < eaters[food].size(); ++j){
          edible[eaters[food][j]]--;
      }
  }

  }

  int solve(){
  best = 987654321;
  vector edible(n);
  search(edible, 0);
  return best;
  }

  int main()
  {
  int tc;
  for(cin >> tc; tc-- > 0;){
  cin >> n >> m;
  vector friend_name(n);
  for(int i = 0; i < n; ++i){
  cin >> friend_name[i];
  }
  for(int i = 0; i < m; ++i){
  int food_like_count;
  cin >> food_like_count;
  eaters[i].resize(food_like_count);
  for(int j = 0; j < food_like_count; ++j){
  string like_friend_name;
  cin >> like_friend_name;
  for(int k = 0; k < n; ++k){
  if(like_friend_name == friend_name[k]){
  eaters[i][j] = k;
  canEat[k].push_back(i);
  break;
  }
  }
  }
  }

  cout << solve() << endl;
  }
  return 0;

  }

  책에 내용대로 구현한것같은데; 런타임에러가 나네요; 스텍 오버플로

  
  9년 전 link

• 
  kloudia

  사실 간단한 문제인데, "주어"와 "목적어"를 정확히 잡지 않고 재귀호출을 해서 많이 헤맸네요...T.T
  "사람을 기준으로 음식을" 이냐, "음식을 기준으로 사람을" 이냐를 명확히 구분하면 간단한 문제였네요.

  
  8년 전 link

• 
  antasis9

  책에는 범위가 20이고, 온라인에는 범위가 50이네요..

  이것때문에 계속 타임 아웃 발생했습니다... ㅠㅠ..

  
  8년 전 link

• 
  taso

  음.. ㅜㅜ.....
  괜히 bit로 set을 표현해서 풀려다가 계속 타임아웃났었네요. 그냥 책에 나온대로하면 됩니다..

  
  6년 전 link

• 
  kabina

  from itertools import combinations
  import sys

  filedata = list()
  testcases = {}
  testcase = list()

  def readdata_new() :
  cases = lambda: sys.stdin.readline()
  for cs in range(int(cases)) :
  tc = list()
  friends, foods = map(int, lambda: sys.stdin.readline().split())
  friendslist = lambda: sys.stdin.readline().split()
  frifod = [friends, foods]
  tc.append(frifod)
  tc.append(friendslist)
  for i in range(0, foods) :
  availfood = lambda: sys.stdin.readline().split()
  tc.append(availfood)
  testcases[str(cs)] = tc

  def readdata() :
  cases = sys.stdin.readline()
  for cs in range(int(cases)) :
  tc = list()
  friends, foods = map(int, sys.stdin.readline().split())
  friendslist = sys.stdin.readline().split()
  frifod = [friends, foods]
  tc.append(frifod)
  tc.append(friendslist)
  for i in range(0, foods) :
  availfood = sys.stdin.readline().split()
  tc.append(availfood)
  testcases[str(cs)] = tc

  def selectfoods(lst, foodcond): ## lst : 조합, foodcond : 음식별 먹을 수 있는 친구들
  selectedfoods = list()
  for f in lst:
  selectedfoods.extend(foodcond[int(f)][1:])
  return selectedfoods

  def getcooks(cond) :

  foodcnt = cond[0][1]
  foodcond = cond[2:2+foodcnt]
  minfood = foodcnt
  lst = list()
  for i in range(2, foodcnt+1) :
      lst = list(combinations(list(j for j in range(int(foodcnt))), int(i)))
      for j in lst :
          friendsname = list(cond[1])
          selectedfoods = selectfoods(j, foodcond)
          for fname in selectedfoods :
              if fname in friendsname :
                  friendsname.remove(fname)
                  if(len(friendsname)==0 and minfood > len(j)) :
                      minfood = len(j)
                      return minfood

  readdata()
  for case in range(len(testcases)) :
  foodcnt = getcooks( testcases[str(case)])
  print(foodcnt)

  python 3.5.3인데.. 제 PC에서는 잘 되는데..
  제출하면 런타임 오류가 나오네요.. 왜그럴까요? ;; ㅠㅠ

  
  6년 전 link

• 
  ozLion

  테스트 data 구할 수 있나요?

  
  6년 전 link

• 
  jspark2

  import operator
  import sys
  rl = lambda: sys.stdin.readline()

  def checkfood(frdlist,cklist,nfood,nfriend):

  flag = True
  for f in frdlist:
      if f==0:
          flag = False
  if flag:
      return 0
  
  bestfood = [0]*nfood
  for i in range(0,nfood):
      for j in range(0,nfriend):
          if cklist[j][i] == 1 and frdlist[j] == 0:
              bestfood[i] = bestfood[i] + 1
  
  max_index, max_value = max(enumerate(bestfood), key=operator.itemgetter(1))
  selectfood = [idx for idx,item in enumerate(bestfood) if item == max_value]
  
  ret = 9999
  for j in range(0,len(selectfood)):
      foodidx = selectfood[j]        
      for i in range(0,nfriend):
          frdlist[i] = frdlist[i] + cklist[i][foodidx]        
  
      tmp = 1 + checkfood(frdlist,cklist,nfood,nfriend)
      ret = min(ret,tmp)
  
      for i in range(0,nfriend):
          frdlist[i] = frdlist[i] - cklist[i][foodidx]        
  return ret

  idx = 0
  n = int(rl())
  while idx < n:
  nfriend,nfood = map(int,rl().split())
  name = rl().split()
  count = {}
  for nm in name:
  count[nm] = 0
  cklist = [[0]*nfood for i in range(0,nfriend)]

  for i in range(0,nfood):
      tmp = rl().split()
      tmp = tmp[1:]
      for j in tmp:
          pos = [idx for idx,item in enumerate(name) if item == j]
          cklist[pos[0]][i] = cklist[pos[0]][i] + 1
  frdlist = [0]*nfriend
  fdhistory = []
  ret = checkfood(frdlist,cklist,nfood,nfriend)
  print(ret)
  idx = idx + 1

  이렇게 풀었는데, 시간초과가 납니다 ㅠㅠ
  checkfood는 greedy algorithm으로
  가장 많은 친구들을 만족시키는 음식들 list를 생성하고
  해당 list에 대해 checkfood를 다시 돌립니다.

  왜 시간초과가 발생할까요?

  
  6년 전 link

• 
  cokepizza

  비트마스크로 풀면 물건 => 사람으로 풀어도 빠르게 통과되네요 물론 사람 => 물건 대응관계로 풀면 더 빠르게 통과됩니다

  
  6년 전 link

• 
  cokepizza

  근데 테스트케이스가 더 있어야할 것 같네요 long범위로 비트마스킹을 해야하는데 잘못해서 Integer범위에서 연산했는데도 통과가 떴습니다. 1 << 32 이상 테스트케이스가 없어 오버플로가 안떴거나 운좋게 오버플로 상태에서도 답이 나왔던 거 같네요 tc추가후 리저지 부탁드립니다

  
  6년 전 link

• 
  hhhhFE

  책에서 남은 친구들 중 가장 많은 사람들이 먹을 수 있는 음식을 선택하는 탐욕법이 최적해를 찾아낼 수 있지 않을 수 있다는데, 어떤 경우가 있나요???

  
  3년 전 link

• 
  woo0722

  이 문제를 보고 어떻게 완전탐색으로 최적화하면 시간초과가 안나겠구나를 알 수 있나요?

  
  4달 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.