글 읽기 - 58%에서 자꾸 틀립니다.(코드 설명 있음)

kibum1024 2년 전 0

몇가지 예시들로 계속 해봤는데 잘 안됩니다.

문제 해결을 전체적으로 말하자면

우선 init() 함수에서 입력을 받고 변수 Wal 에 내가 갖고 있는 스티커의 총 가격을 구합니다.

그다음에 makeLR() 함수에서 왼쪽 절반과 오른쪽 절반을 나누어 각 절반에서 만들 수 있는 모든 가격과 가치를 저장하고 정렬합니다. (lef / rig)

이후 가격은 높은데 가치는 낮은 경우의 수를 전부 지워서 저장합니다. (Le / Ri)

마지막으로 main 함수에서 Le의 경우를 다 보면서 각 경우에서 전체 가치가 K를 이상이 되는 가장 작은 가격을 이분탐색으로 구하고

모든 이분 탐색에서의 최소값을 답으로 반환하도록 하였습니다.

#include<bits/stdc++.h>
#define INF 9000000000000000000
using namespace std;
typedef long long ll;
struct sti{
  ll cost,val;

  bool operator<(sti A){
    if(cost == A.cost) return val>A.val;
    return cost<A.cost;
  }

  sti operator +(sti A){
    sti res;
    res.cost = cost+A.cost;
    res.val = val+A.val;
    return res;
  }

};
int N,wn;
vector<sti> stick,lef,rig,Le,Ri;
ll K,Wal,ans=INF;

void init(){ // 초기 입력 과정
  cin >> N;
  int i,x;
  ll temp;
  for(i=0;i<N;i++){
    scanf("%lld",&temp);
    stick.push_back({temp,0});
  }
  for(i=0;i<N;i++){
    scanf("%lld",&temp);
    stick[i].val = temp;
  }
  scanf("%lld\n%d",&K,&wn);
  for(i=0;i<wn;i++){
    scanf("%d",&x);
    Wal+=stick[x].cost; // 현재 내가 보유하고 있는 스티커를 모두 돈으로 바꿨을 때의 가격
  }
}

sti func(int st,int mask){ //비트마스크를 이용하여 특정 경우에 대한 가격과 가치를 반환
  sti res = {0,0};
  int i=st;
  while(mask){
    if(mask&1) res = res+stick[i];
    mask/=2;
    i--;
  }
  return res;
}

void makeLR(){ // 반씩 나누어 각각 만들 수 있는 가격과 가치의 경우의 수를 계산
  int mid = (N+1)/2;
  int i;
  for(i=0;i<(1<<mid);i++){
    lef.push_back(func(mid-1,i));
  }
  for(i=0;i<(1<<(N-mid));i++){
    rig.push_back(func(N-1,i));
  }
  sort(lef.begin(),lef.end());
  sort(rig.begin(),rig.end());
  
  // Le, Ri 벡터는 가격은 높은데 가치가 낮은 경우는 사용될 수 없으니 이를 뺀 벡터
  ll Val = -1;
  for(i=0;i<lef.size();i++){
    if(Val<lef[i].val){
      Le.push_back(lef[i]);
      Val = lef[i].val;
    }
  }
  Val = -1;
  for(i=0;i<rig.size();i++){
    if(Val<rig[i].val){
      Ri.push_back(rig[i]);
      Val = rig[i].val;
    }
  }
  
}
int main(){
  init();
  makeLR();
  
  int i,mi,le,ri;
  for(i=0;i<Le.size();i++){
    sti cur = Le[i];
    le = 0; ri = Ri.size()-1;
    while(le!=ri){ // 이분탐색을 통해 cur에 대해서 가치의 합이 K이상이 되는 최소 가격을 구하는 과정
      mi = (le+ri+1)/2;
      if(Ri[mi].val<K-cur.val) le = mi;
      else ri = mi-1;
    }
    if(le == Ri.size()-1) continue;
    ans = min(ans,cur.cost+Ri[le+1].cost);
  }
  
  if(ans==INF) printf("-1");
  else if(Wal>ans) printf("0"); // 보유하고 있는 가격이 최소로 가져야할 가격보다 많으면 0출력
  else printf("%lld",ans-Wal); // 이외에는 보유하고 있는 가격을 제외한 가격을 출력
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

58%에서 자꾸 틀립니다.(코드 설명 있음)

kibum1024 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말