C언어 232제] 유리 구슬(Marbles)

출처 : 반크_반크 20년 백서

 

문제]

나는 유리 구슬을 모으는데, 그 구슬들을 담아놓을 상자를 사려고 한다. 상자는 두 가지 유형으로 나눌 수 있다.

타입 1: 하나에 C1 달러며 정확하게 n1개의 구슬을 담을 수 있다.
타입 2: 하나에 C2 달러며 정확하게 n2개의 구슬을 담을 수 있다.

각 상자에는 정확하게 주어진 용량만큼의 구슬을 집어넣을 것이며, 총비용은 최소한으로 줄였으면 한다. 여러 상자에 구슬을 나눠 담는 가장 좋은 방법을 찾아보자.

입력
입력 파일에는 테스트 케이스가 여러 개 들어갈 수 있다. 각 테스트 케이스는 정수 n(1 이상 2,000,000,000 이하)이 들어있는 줄로 시작한다. 그 다음 줄에는 Ci과 ni이, 그 다음 줄에는 C2와 n2가 입력된다. 여기에서 C1, C2, n1, n2는 모두 양의 정수며 2,000,000,000보다 작다.
구슬의 개수를 입력하는 자리에 0이 들어오면 입력이 종료된다.

출력
입력에 있는 각 테스트 케이스에 대해 비용을 최소하할 수 있는 해법을 출력한다(한 줄에 테스트 케이스 하나씩). 해법이 있으면 두 개의 음이 아닌 정수 m1, m2를 출력한다. 이때 mi는 타입 i인 상자의 개수를 의미한다. 해가 없으면 "failed"를 출력한다.
해가 존재하면 그 해가 유일한 해라고 가정해도 된다.

입력 예
43
1 3
2 4
40
5 9
5 12
0

출력 예
13 1
failed


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제55 유리 구슬 (Marbles) p200

 

참고풀이]

#include <stdio.h>

int main()
{
   int N, c1, c2, n1, n2, m1, m2;
   int tmp;
   int chk;

   while(scanf("%d",&N), N!=0)
   {
      scanf("%d%d",&c1, &n1);
      scanf("%d%d",&c2, &n2);

      chk=0;
      //용량대 가격비가 싼 것을 c1, n1으로 놓는다.
      if((double)c1/(double)n1 > (double)c2/(double)n2) 
      {
         tmp=c1, c1=c2, c2=tmp;
         tmp=n1, n1=n2, n2=tmp;
         chk=1;
      }

      //그리디 알고리즘을 사용하여 해결한다.
      //구슬을 최대한으로 담을 수 있는 첫번째 상자의 개수를 구한다.
      m1=N/n1;

      //loop는 구슬을 최대한으로 담을 수 있는 첫번째 상자의 개수에서
      //두 번째 상자의 크기를 뺀 수만큼만 돌면된다.
      for(;m1>=N/n1-n2 && m1>=0; m1--) 
      {
         //첫번째 상자의 개수를 하나씩 줄여가면서 그 상자에 최대한
         //담고 남는 구슬들을 두번째 상자로 채운다.
         m2=(N-m1*n1)/n2;
         if(N==m1*n1+m2*n2) break; //남는 구슬이 없으면 break 
      }

      if(N==m1*n1+m2*n2)
      {
         if(chk==0) printf("%d %d\n",m1,m2);
         else printf("%d %d\n",m2,m1);
      }
      else
         printf("failed\n");
   }
   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 겨울