[SW Expert Academy, SWEA 13736] 사탕 분배 (java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX8BB5d6T7gDFARO&categoryId=AX8BB5d6T7gDFARO&categoryType=CODE&problemTitle=13736&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

---

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

728x90

---

A가 몇 개이던 B가 몇 개이던 A+B는 동일하다. 분배 후에 A의 개수를 A’, B의 개수를 B’이라고 한다면, A+B = A’+B’이다.

 

A가 더 적었다고 하면 A’=2A이고, B’=2B % (A+B)이다.

ex) A=2, B=8 → A’=4, B’=16%10=6

 

즉, 이 문제의 접근은 두 사람 다 사탕의 개수를 2배로 만들고, 전체 사탕 수보다 많이 가지고 있는 사람은 전체 사탕 수만큼 압수한다고 생각하면 된다.

A → (A x 2) % (A + B)

B → (B x 2) % (A + B)

 

이 규칙을 적용하면 양 쪽에 동일한 연산을 할 수 있다.

또한 2번의 수행 결과를 (A x $2^2$) % (A + B), (B x $2^2$) % (A + B)로 한 번의 연산으로 구할 수 있고,

4번의 수행 결과를 (A x $2^4$) % (A + B), (B x $2^4$) % (A + B)로 한 번의 연산으로 구할 수 있다.

 

따라서 k번의 수행을 $2^k$를 곱하는 한 번의 연산으로 끝낼 수 있고, 따라서 이 문제의 핵심을 $2^k$를 빠르게 구하는 것이다.

또한 B’=A+B-A’이기 때문에 답은 min(A’, A+B-A’)으로 구할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	
	static long mod;

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			long A = Long.parseLong(st.nextToken());
			long B = Long.parseLong(st.nextToken());
			long K = Long.parseLong(st.nextToken());
			
			// 2 ^ K 구하기
			mod = A + B;
			long kp = power(K);
			// A' = (A * 2 ^ K) % (A + B) 구하기
			A = (A * kp) % mod;
			long result = Math.min(A, mod - A);
			sb.append("#").append(tc).append(" ").append(result).append("\n");
		}
		System.out.println(sb);
	}

	private static long power(long n) {
		if(n == 1) return 2;
		
		long ret = power(n / 2);
		ret = (ret * ret) % mod;
		if((n & 1) == 1) ret = (ret * 2) % mod;
		
		return ret;
	}
}