https://www.acmicpc.net/problem/1904solved.ac 기준 실버 3의 쉬운 문제입니다.4년 전에 실패했던게 까먹고 남겨져 있어서 다시 풀었습니다.#풀이 과정1 이상 1,000,000 이하의 어떤 자연수 n이 주어졌을 때, 2 종류의 타일 '00' 과 '1'로 만들 수 있는 크기가 n인 수열의 총 가짓 수를 구하는 문제입니다.처음에는 어떤 수열의 앞 뒤에 타일을 붙일 때 발생하는 중복을 따로 처리해야 하나 싶었으나, 생각해보면 모든 수열은 오로지 뒤에만 타일을 붙여나감으로써 만들 수 있다는 사실을 알 수 있습니다. 예를 들어 '001'은 '1' 앞에 '00'을 붙여서 만들 수 있지만 이는 '00' 뒤에 '1'을 붙여서 만든 것과 같습니다. '00001'과 같은 수열 또한 '00..

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 자료형의 범위를 한참 넘어갈 수 있습니다. 이를 해결하는데에는 다음과 같은 모듈러 연산의 성질을 이용할 수 있습니다. $$(A\ast B)modn=(Amodn\ast Bmodn)modn$$ 이 성질을 이용하면, $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..