티바이트



문제 링크 : https://www.algospot.com/judge/problem/read/POTION

(알고스팟)


문제 이해

어떤 약을 한 단위 만드는 데 필요한 n개의 재료들의 양과

현재 넣은 재료의 양이 입력된다.

이 때 약을 만들기 위해 더 넣어야 하는 재료들의 양을 구하는 문제이다.

입력값은 모두 정수이고,

약을 최소한 1단위 이상은 만들어야 한다.



풀이

완성한 약의 양이 꼭 정수단위일 필요가 없다는 점에 주의해야 한다.

따라서 필요한 재료들의 양을 최대공약수로 나누어

들어가야 하는 재료들의 비를 구했다.


예를 들어 들어가야 하는 3가지 재료의 양이 각각 2 4 6 이라면

최대공약수 2로 나누어 1 2 3 라는 비율을 구한다.

이제 들어가야 하는 재료의 양은 1 2 3 의 정수배인

1 2 3

2 4 6

3 6 8

4 8 10

...

...

과 같이 된다.

(정수배인 이유는 입력되는 재료의 양이 정수이므로)


그런데 문제에서 완성 약을 한 단위 이상 만들어야 한다는 조건이 있으므로

2 4 6 다음부터 검사하면 되는것이다.


여기서 현재 넣은 재료가 3 6 7 이라면

재료추가로 만들 수 있는 값이 위 정수배들 중에서 3 6 8 이므로

약을 완성시키기 위해 0 0 1 만큼의 재료를 더 넣어야 하는 것이다.


최대공약수를 구하는 부분은 유클리드 알고리즘을 사용하였고,

n개 수의 GCD를 구하기 위해 해당 알고리즘을 n-1번 반복하였다.

(관련글 : http://www.tibyte.kr/224)



코드

 

#include <cstdio>

#include <cmath>


using namespace std;


//GCD계산 (유클리드)

int calcGcd(int n1, int n2)

{

int temp;

if (n1 < n2) {

temp = n1;

n1 = n2;

n2 = temp;

}

while (n2 != 0) {

temp = n1%n2;

n1 = n2;

n2 = temp;

}


return n1;

}



int main(void)

{


int numTry;

scanf("%d",&numTry);


while (numTry--)

{

int numElem;

scanf("%d",&numElem);


int *ideal = new int[numElem];

int *curr = new int[numElem];

int gcd;

double curMul = 0;

double maxMul = 0;

int mul;

//비율값 입력받음

for (int i = 0; i < numElem; i++) 

scanf("%d", &ideal[i]);



//비율값의 gcd계산

gcd = ideal[0];

for (int i = 1; i < numElem; i++) 

gcd = calcGcd(gcd, ideal[i]);



//ideal값 재계산

for (int i = 0; i < numElem; i++)

ideal[i] = ideal[i]/gcd;


//현재넣은값 입력받음

for (int i = 0; i < numElem; i++) {

scanf("%d", &curr[i]);

curMul = (double)curr[i] / ideal[i];

if (curMul >maxMul ) maxMul = curMul;

}

mul = ceil(maxMul);

for (int i = 0; i < numElem; i++) {

ideal[i] *= mul;

printf("%d ", ideal[i] - curr[i]); 

}

printf("\n");


}

return 0;

}











 


댓글을 다는 공간입니다. (로그인하지 않아도 댓글을 남길 수 있습니다.)



게시판 목록은 좌측상단에 있습니다.

09-28 09:44