백준/수학 (28) 썸네일형 리스트형 백준 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") .. 백준 2381 - 최대 거리 https://www.acmicpc.net/problem/2381 서론 이 문제에서 써야 하는 테크닉은 은근 Well-Known이라고 한다. 대회를 준비하는 사람이라면 한 번쯤 익혀둘 필요가 있다. 식 전개 서로 다른 두 점의 좌표를 각각 $(x_{i}, y_{i}), (x_{j}, y_{j})$라고 하자. 그러면 두 점의 맨해튼 거리는 $|x_{i} - x_{j}| + |y_{i} - y_{j}|$임은 너무나도 잘 알고 있다. 자 여기서 신기한 걸 해보자. 우리는 $max(|x_{i} - x_{j}| + |y_{i} - y_{j}|)$를 구할 건데 절댓값을 어떻게 없앨까? 절댓값을 없애기 위해 다음과 같은 전개가 가능하다. $max(|x_{i} - x_{j}| + |y_{i} + y_{j}|) = ma.. 이전 1 2 3 4 ··· 6 다음
