![]()
1. 방 배정 https://www.acmicpc.net/problem/13300 학생들을 학년별, 성별로 한 방에 배정하려고 하는데 필요한 최소 방의 개수를 구하는 문제다. 문제에서 요구하는 대로 학년별, 성별로 인원을 센 다음에 각각에 대해 최소로 필요한 방의 개수를 센 뒤 더해주면 된다. 이는 나눗셈과 나머지 연산으로 쉽게 구할 수 있다. #include int n, k, s, y, C[7][2]; int main() { scanf("%d%d", &n, &k); while (n--) { scanf("%d%d", &s, &y); ++C[y][s]; } int ans = 0; for (int i = 1 ; i
문제 링크 https://www.acmicpc.net/problem/1090 문제 요약 \(N\)개의 점이 주어진다. 이 때 적어도 한개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수 , 적어도 두 개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수, ... 적어도 \(N\)개의 점이 한 점위에 있게 하기위해 움직이는 최소 횟수를 구하는 문제다. 문제 풀이 모든 점을 모으는 것이 아니라는 것이 이문제를 어렵게 만드는 요소 중 하나다. 하지만 모든 점을 모으는데 있어 최선의 선택은 \(x\)좌표들의 중앙값, \(y\)좌표들의 중앙값으로 모이는게 최선이라는 생각을 살짝 변형하면 쉽게 풀 수 있다. (\(N\)개의 점을 모두 모으는데 왜 중앙값이 최선이냐에 대해서는 완벽하게 증명을 하진 못하겠다...
문제 링크 https://www.acmicpc.net/problem/2271 문제 요약 자연수로 이루어진 크기 \(N\)인 배열 \(A\)가 주어진다. 이 때 \(1\leq P\ \lt\ Q\ \lt\ R\ \lt\ S\ \leq\ N\)을 만족하는 \(P\), \(Q\), \(R\), \(S\)에 대해 아래 두가지 수식이 만족하는 경우가 있는지 찾는 문제다. 1. \(A[Q]\ \lt\ A[S]\ \lt\ A[P]\ \lt\ A[R]\) 2. \(A[Q]\ \gt\ A[S]\ \gt\ A[P]\ \gt\ A[R]\) 문제 풀이 우선 2번 경우는 생각하지 말고 1번 경우만 생각해 보도록 하자. \(i\lt j\) 인 임의의 \(i\), \(j\)를 선택했다고 하자. 만약 \(A[i] \lt A[j]\)를..
