동전 옮기기(알고리즘)

동전 옮기기

 

동전주머니에 있는 동전들을 얼마만큼 최소적으로 이동을 해서 각 주머니 동전개수가 같아지게 하게끔 하는 알고리즘 문제입니다.

우선 입력 case를 봅시다.

 

첫 행:TestCase 수(testCases)

각 케이스의 첫 번째 행: 동전 주머니 개수(numPockets)

각 케이스의 두 번째 행 이후:주머니에 들어있는 동전 개수(eachPocket이라는 주머니에 삽입)

input.txt

 

2(testCases)

5(주머니 개수)

1(동전들)

1(동전들)

1(동전들)

1(동전들)

6(동전들)

2(주머니 개수)

1(동전들)

3(동전들)

 

 

결과

4(최소 움직인 횟수)

1(최소 움직인 횟수)

 

우선 이를 풀기위해서 평균값이라는 원리를 이용해야합니다.

즉 주머니에 있는 동전들의 총합을 주머니의 개수로 나누어 평균값을 구합니다. 이 평균값과 배열 값들의 차이가 얼마나 나는지를 통해 문제를 풀면되겠습니다.

 

예를 들어 A주머니와 B주머니가 있습니다. 두 주머니 동전 합의 평균이 3이라고 치면 A주머니는 3보다 많은 5개 B주머니는 3보다 적은 1개가 있다고합니다. A주머니는 평균값보다 크므로 줄이고 그에따라 보존의 법칙으로 B주머니는 커집니다. 즉 동전 개수의 평균값과 배열 요소 값이 같으면 굳이 비교 할 필요가 없습니다. 코드로 자세히 살펴볼게요.

 

 

freopen함수를 통해 input.txt파일을 열어서 입력을 파일로 변환시킵니다.

scanf를 통해 testCases에 테스트케이스 수를 받습니다.

 

 

 

입력받은 테스트케이스 수만큼 전체 for문을 돌립니다.

첫 번째 케이스의 경우

scanf를 통해 마찬가지로 주머니 개수를 num_Pockets에 담습니다.

그 수만큼 for문을 돌려서 우선 eachPocket 배열에 각 주머니마다 동전개수들을 입력받고

그 개수를 총 합을 구합니다. totalBeans는 동전의 총 합입니다. 이 총합은 평균을 구할때 유용하겠지요.

 

만약 동전 총 합을 주머니 개수로 나눈 나머지가 주머니 개수보다 크다면 즉 주머니 개수랑 동전 개수 총합이 1만 차이 날 경우

이동할 필요가없기에 -1을 줍니다.

만약에 이동을 해야한다면

전체 동전 개수를 주머니 개수로 나눠서 평균값을 구합니다.

이 평균값과 각 주머니에 동전 개수들의 차이를 구합니다.(averBeans-eachPocket[j])

이를 출력해주고 누적 이동 횟수를 구해줍니다.

 

 

아래는 전체 총 코드입니다.