문제 1: 교차 부호 수열의 합
길이 n의 연속된 정수 수열 1, 2, 3, ... n에 대해, 매 m개마다 부호를 교차시키는 수열을 정의합니다. 초기 부호는 음수(-)이며, 부호는 -, -, ..., +, +, -, -, ... 순서로 반복됩니다. 이때 처음 n개 항의 총합을 구하는 문제입니다.
입력 조건: 두 정수 n, m (2 ≤ n ≤ 10⁹, 1 ≤ m), n은 2m으로 나누어 떨어짐
출력: 처음 n개 항의 합
핵심 아이디어: 수학적 귀납을 통해 합의 공식을 유도할 수 있습니다. 2m개를 하나의 주기로 보면, 각 주기의 합은 m × (2m) = 2m²입니다. 전체 주기 수는 n/(2m)이므로, 총합은 (n/(2m)) × 2m² = mn/2입니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class SignAlternatingSum {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tokens = br.readLine().trim().split("\\s+");
BigInteger total = new BigInteger(tokens[0]);
BigInteger group = new BigInteger(tokens[1]);
// 합 = m * n / 2
BigInteger result = total.multiply(group).divide(BigInteger.valueOf(2));
System.out.println(result);
}
}문제 2: 최적 전략 카드 게임
n장의 카드가 주어지며, 각 카드에는 숫자가 적혀 있습니다. 두 플레이어가 번갈아가며 한 장씩 뽑으며, 자신의 점수에 누적합니다. 모두 최적의 전략을 사용할 때, 선공 플레이어 점수에서 후공 플레이어 점수를 뺀 값을 구합니다.
핵심 아이디어: 최적 전략은 매 턴 가장 큰 수를 가져가는 것입니다. 따라서 내림차순 정렬 후, 짝수 인덱스(0, 2, 4...)는 선공, 홀수 인스는 후공이 가져갑니다. 시간 복잡도 O(n log n)이 필요합니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
public class OptimalCardGame {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine().trim());
int[] values = new int[count];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < count; i++) {
values[i] = Integer.parseInt(st.nextToken());
}
// 내림차순 정렬
Arrays.sort(values);
reverseArray(values);
int diff = 0;
for (int i = 0; i < count; i++) {
if ((i & 1) == 0) {
diff += values[i]; // 선공 턴
} else {
diff -= values[i]; // 후공 턴
}
}
System.out.println(diff);
}
private static void reverseArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
}
}
}문제 3: 초콜릿 배분 문제
N일 동안 M개의 초콜릿을 먹어야 합니다. 매일 먹는 양은 전날의 절반 이상이어야 하며(올림), 모든 날 최소 1개 이상 먹어야 합니다. 첫날 먹을 수 있는 최대 초콜릿 수를 구합니다.
핵심 아이디어: 날 먹는 양을 기준으로 시뮬레이션하면 O(N)이고, 이를 이분 탐색으로 최적화하여 O(N log M)으로 해결합니다. 특히 N=1인 경우를 주의해야 합니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class ChocolateDistribution {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int days = Integer.parseInt(st.nextToken());
int total = Integer.parseInt(st.nextToken());
// 이분 탐색으로 첫날 최대값 탐색
int low = 1, high = total;
int answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (canSurvive(days, total, mid)) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(answer);
}
// firstDay개로 days일 동안 total개를 다 먹을 수 있는지 검증
static boolean canSurvive(int days, int total, int firstDay) {
long remaining = total;
long daily = firstDay;
for (int i = 0; i < days; i++) {
remaining -= daily;
if (remaining < 0) return false;
daily = (daily + 1) / 2; // 올림 나눗셈
}
return true;
}
}문제 4: 플레이리스트 구성
길이 A인 곡 X개, 길이 B인 곡 Y개가 있습니다. 총 길이가 정확히 K인 플레이리스트를 만들 수 있는 경우의 수를 구합니다. 각 곡은 최대 한 번 사용되며, 순서는 고려하지 않습니다.
핵심 아이디어: A타입을 i개 선택하면 B타입은 (K-A×i)/B개 필요합니다. 가능한 모든 i에 대해 조합 수 C(X,i) × C(Y, (K-A×i)/B)를 합산합니다. 큰 수 처리를 위해 모듈러 연산과 BigInteger를 사용합니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
public class PlaylistCombination {
static final BigInteger MOD = BigInteger.valueOf(1_000_000_007);
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int targetLen = Integer.parseInt(br.readLine().trim());
StringTokenizer st = new StringTokenizer(br.readLine());
int lenA = Integer.parseInt(st.nextToken());
int cntA = Integer.parseInt(st.nextToken());
int lenB = Integer.parseInt(st.nextToken());
int cntB = Integer.parseInt(st.nextToken());
BigInteger result = BigInteger.ZERO;
// A타입을 i개 선택하는 경우 탐색
for (int pickA = 0; pickA <= cntA; pickA++) {
int remaining = targetLen - lenA * pickA;
if (remaining < 0) break;
if (remaining % lenB != 0) continue;
int pickB = remaining / lenB;
if (pickB > cntB) continue;
// C(cntA, pickA) * C(cntB, pickB)
BigInteger waysA = nCr(cntA, pickA);
BigInteger waysB = nCr(cntB, pickB);
result = result.add(waysA.multiply(waysB)).mod(MOD);
}
System.out.println(result);
}
// 조합 계산: nCr = n! / (r! * (n-r)!)
static BigInteger nCr(int n, int r) {
if (r < 0 || r > n) return BigInteger.ZERO;
if (r == 0 || r == n) return BigInteger.ONE;
r = Math.min(r, n - r);
BigInteger numerator = BigInteger.ONE;
BigInteger denominator = BigInteger.ONE;
for (int i = 0; i < r; i++) {
numerator = numerator.multiply(BigInteger.valueOf(n - i));
denominator = denominator.multiply(BigInteger.valueOf(i + 1));
}
return numerator.divide(denominator).mod(MOD);
}
}