Processing math: 76%

본문 바로가기

백준/수학

(34)

백준 27437 - 분수찾기 2 https://www.acmicpc.net/problem/27437힌트더보기문제에 그려진 테이블을 유심히 보자. 위와 같이 구분한다고 했을 때 패턴을 찾아낼 수 있는가?풀이더보기위 힌트에서 주어진 테이블을 대각선으로 나눴다. 그러면 우리는 각 대각선에서 발견할 수 있는 중요한 성질을 다음과 같이 정리할 수 있다. 각 대각선에 속한 수들의 집합을

$D_{1}, D_{2}, D_{3}, ...$ 으로 부르며 원소의 갯수는

$1, 2, 3, ...$ 이다. 이때

$D_{i}$ 의 원소인

$\frac{y}{x}$ 에서

$MAX(x, y) = i$ 이다. 우리는

$\sum_{i = 1}^{n}\nolimits i \leq X$ 를 만족하는

$i$ 의 최댓값을 파라메트릭 서치로 찾아낼 수 있다. 그리고 대각선을 문제의 규칙에..

백준 18287 - 체스판 이동 https://www.acmicpc.net/problem/18287 규칙 살펴보기 홀수 행와 짝수 행일 때의 이동은 그림으로 나타내면 다음과 같다. 문제에 아래로 가는 것만 가능하다 했으므로 다른 이동은 무시한다. 그러면 우리는 이 이동을 표현한 전이 행렬을 구상할 수 있다. MATRIX[i][j] := 현재 행의 i열에서 다음 행의 j열로 가는 경우의 수 그러면

$M^{2}$ 크기의 전이 행렬 두 개를 만들 수 있다. 이동 합성 행렬을 만든 건 좋은데 이 따로국밥인 행렬들을 어떻게 처리할지 난감하다. 이럴 때는 그냥 홀수 행 전이 행렬과 짝수 행 전이 행렬을 곱해 2번 이동하는 행렬을 만들면 된다. 그러면 우리는 2칸씩 이동하는 행렬을 표현했으므로 남은건 행렬 거듭제곱을 통해 이동 횟수 계산을 $O(M..

[ICPC] 백준 9341 - ZZ https://www.acmicpc.net/problem/9341 조건 정리 일단 문제를 편하게 풀기 위해 ZZ(0, 0)을 정의할 필요가 있다.

$ZZ(0, 0) = b - a$ 로 둔다.(피보나치수열을 생각한다.) 직접 해보기 10 * 10 테이블을 단순한 dp로 출력해보자. 그러면 다음 발견을 할 수 있다. 어떤 항은 위처럼 Z 모양으로 더한 결과와 같다. 수식으로 나타내면 다음과 같다.

$ZZ(a, b) = [\sum\limits_{i = 0}^{a}ZZ(i, b - 1)] + ZZ(0, b - 2)$ 그러면 우리는 위 식의 전개를 행렬로 표현할 수 있다. 예를 들어 c가 2인 경우 아래처럼 된다. $\left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\..

백준 10986 - 나머지 합 https://www.acmicpc.net/problem/10986 힌트 더보기

$(A - B) \mod m = (A \mod m) - (B \mod m)$ 풀이 더보기 나머지의 성질에 대해 생각하면

$(A - B) \mod m = (A \mod m) - (B \mod m)$ 가 성립됨을 알 수 있을 것이다. 이를 문제에 적용하면 모듈러 값이 같다는 건 둘을 뺐을 때 0이 된다는 소리고 즉, pref[A] - pref[B]가 m으로 나누어진다는 것이 된다. 따라서 우리는 누적합을 계산하면서 각 나머지의 횟수를 세주고

$\binom{N}{2}$ 을 모두 계산해주면 된다. 참고로 나머지가 0인 경우는 이미 나누어진 것이므로 이거는 따로 더해주도록 한다. 물론 이항 계수의 계산에도 포함해야 한다. 전체 코드 ..

백준 14848 - 정수 게임 https://www.acmicpc.net/problem/14848 포함 배제의 원리를 이용해 집합에서 원소들을 지워나가는 문제이다. 단, 이 문제는 서로 배수 관계인 수가 있을 수 있으므로 원소들을 곱할 때 최소공배수를 계산해야 올바른 답을 얻을 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma") ..

이전 1 2 3 4 5 ··· 7 다음 2/7

티스토리툴바