https://www.acmicpc.net/problem/2467 #풀이 입력이 10만개이므로 완전 탐색은 불가능합니다. 그런데 잘 생각해보면 아무 두 용액을 섞었을때 특성값이 양수면 값을 줄여야 0에 가까워지고, 특성값이 음수이면 값을 늘려야 0에 가까워집니다. 따라서, 정렬한 용액 배열에서 첫 인덱스와 마지막 인덱스에 두 개의 포인터를 설정하고, 특성값이 0에 가까워지도록 포인터를 한 칸씩 움직이면서 절댓값이 가장 작은 특성값을 갱신하면 문제에서 요구하는 두 용액을 찾을 수 있습니다. 문제에서 주어지는 배열은 이미 오름차순 정렬이 되어있으므로, 특성값이 양수면 오른쪽 포인터를 1 줄이고, 특성값이 음수이면 왼쪽 포인터를 1 늘립니다. #코드 #include #include #include #inclu..

풀이 간단해보이는 문제지만 solved.ac 기준 난이도가 실버 I인만큼 그렇게까지 간단하게 풀리는 문제는 아닙니다. 가장 단순한 방법으로는 A를 B번 곱하고 C로 나머지 연산을 하는 방법이 있으나, B가 최대 2^31 - 1이므로 반복문을 돌릴때 시간초과가 나게 됩니다. 또한, \( A^B \)의 값이 int나 long long 자료형의 범위를 한참 넘어갈 수 있습니다. 이를 해결하는데에는 다음과 같은 모듈러 연산의 성질을 이용할 수 있습니다. $$ \left(A*B\right)\bmod n=\left(A\bmod n*B\bmod n\right)\bmod n $$ 이 성질을 이용하면, \( A^B \)를 지수가 2의 거듭제곱인 형태로 분해할 수 있습니다. 예를 들어서, \( 2^{11} \bmod 3 ..

새해 기념 첫번째 포스팅입니다. 작년 KOI 중등부 첫번째 문제도 비슷했던 것으로 기억이 나는데, 이 문제가 좀 더 쉬웠던 것 같습니다. 문제의 목표는 자른 색종이가 전부 하얀색이거나 파란색이 될때까지 색종이를 반으로 계속 자르고 나서 그 잘라진 하얀색 / 파란색 색종이의 개수를 구하는 것입니다. #풀이 한 변의 길이가 모두 2의 거듭제곱 형태이기 때문에, 좌표를 바꾸고 길이를 계속 절반으로 하는 재귀함수를 구현하면 될 것 같습니다. 구체적으로는, 1. N x N 사이즈의 정사각형 내에 있는 모든 칸의 색을 체크합니다. 2 - 1. 만약 모든 색이 같다면, 해당 색의 색종이 개수에 1을 더해줍니다. 2 - 2. 만약 한 칸이라도 색이 다르다면, N x N 사이즈의 색종이를 위 그림처럼 (N/2) x (N..