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..

프로그래밍 관련 글을 올리는 블로그입니다. PS를 하다가 문득 회고할 곳이 있으면 좋을 것 같아서 예전에 만들었던 블로그를 다시 시작하게 되었습니다. 글쓰기와 문제풀이 실력이 좀 걱정이지만 하다보면 괜찮아질거라 믿습니다.

풀이 간단해보이는 문제지만 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..