본문 바로가기

분할 정복을 이용한 거듭제곱

 (108)
백준 27299번: 헌내기 현철 https://www.acmicpc.net/problem/27299 27299번: 헌내기 현철 불과 몇 달 전만 해도 새내기였던 현철이는 $22$학번을 이십이학번이 아닌 이이학번으로 읽는다는 것을 신기하게 생각했다. 그런데, 이제 $23$학번이 들어온다는 소식에 현철이는 큰 충격에 빠졌 www.acmicpc.net 구해야 하는 값은 $A^{B^{C}}$를 $10^{7}$으로 나눈 나머지입니다. 여기까지는 생각하기 매우 쉽지만, $C$의 범위가 매우 큽니다. Euler's Theorem을 반복하여 적용할 수 있지만, 저는 그냥 한 번만 적용하고 끝내는 게 더 편할 수도 있다는 생각을 했습니다. 왜냐하면 17315번 에서 이미 한 번 구현했기 때문입니다 ㅎㅎ.. 주의할 점은 엣지 케이스인데, $$A^{B^{..
백준 14679번: 영우와 '갓4' https://www.acmicpc.net/problem/14679 14679번: 영우와 ‘갓4’ 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 몬스터의 수 N이 주어진다. (1 ≤ N ≤ 50,000,000) 두 번째 줄에는 영우가 키우는 캐릭터의 공격력(A), 방어력(D), 최대 체력(H)이 차례대로 www.acmicpc.net $N$이 매우 크지만, 풀이는 생각보다 단순한 문제입니다. 우선 가장 나이브하게 $O(N(A_{p}+D_{p}+H_{p}))$ 또는 $O(N\log(A_{p}D_{p}H_{p}))$으로 매번 몬스터의 공격력, 방어력, 체력을 시뮬레이션하는 것은 시간제한을 통과할 수 없어보입니다. 그런데 어차피 $A_{k} \; D_{k} \; H_{k}$는 각각 1부터 100, ..
백준 17315번: Matrix Game (matrix interpretation) https://www.acmicpc.net/problem/17315 17315번: Matrix Game The input will contain the six integers n, m, a, b, c, and d. www.acmicpc.net National Olympiad in Informatics, China, 2013, Day2에 Problem1로 출제된 문제라고 합니다. 이 문제에 대해 행렬을 사용한 점화식, 일반적인 정수 계수 점화식 두 방법을 이용하여 풀었는데, 복잡도는 비슷하지만 상수 차이로 실행시간 차이가 컸습니다. 그리고 두 풀이가 꽤 상이한 듯하여 둘 다 소개하고자 합니다. 정수 거듭제곱 풀이에 대해 궁금하신 분은 이쪽 링크를 이용하시면 됩니다: Matrix Game (integer i..
백준 9556번: 수학 숙제 https://www.acmicpc.net/problem/9556 9556번: 수학 숙제 각 테스트 케이스마다 조건을 만족하는 N자리 정수의 개수를 1,000,000,007로 나눈 값을 출력한다. www.acmicpc.net 처음엔 포함 배제로 풀려고 했다가, 제가 포함 배제에 익숙하지 못해서 구현을 포기하고 다른 방법으로 풀게 됐습니다. 이 문제의 첫 번째 포인트는 $N$자리 수는 한 개 이상의 0으로 시작할 수 있다는 것입니다. 즉 우리가 체크해야 할 수의 범위는 0부터 $10^{N}-1$까지입니다. 두 번째 포인트는 이 문제의 나눠 떨어진다는 표현은 나머지가 0이라는 것입니다. 그래서 0은 모든 양의 정수로 나누어 떨어지는 수라고 합니다. 이 문제는 물론 포함 배제로도 풀 수 있겠지만, 더 쉬운 관..
백준 16201번: 발코니 공사 https://www.acmicpc.net/problem/16201 16201번: 발코니 공사 첫째 줄에 별장 발코니의 크기 R, C와 부서지지 않은 칸의 개수 K가 주어진다. (1 ≤ R ≤ 1,000,000,000, 2 ≤ C ≤ 1,000,000,000, 0 ≤ K ≤ 1,000) 둘째 줄부터 K개의 줄에는 부서지지 않은 칸의 위치가 공백 www.acmicpc.net 도미노의 모양새에 대한 조건이 너무 강력해서 티어가 낮아진 문제입니다. 이 문제는 colorless한 $1 \times 2$ 도미노의 타일링을 다루고 있고 특별한 조건으로 "가로로만 놓을 수 있음"이 있습니다. 또 하나의 조건은 도미노를 최대한 많이 써야만 한다는 것입니다. 그래서 각 row에 대해 총 몇 개의 도미노를 놓을 수 있는지..
백준 26132번: Fair Division https://www.acmicpc.net/problem/26132 26132번: Fair Division After sailing the Seven Seas and raiding many ships, Cap’n Red and his crew of fellow pirates are finally ready to divide their loot. According to ancient traditions, the crew stands in a circle ordered by a strict pirate hierarchy. Cap’n Red starts by www.acmicpc.net 비록 해당 대회에서 제일 약한 급의 문제이긴 하지만 ICPC World Finals 2021 문제입니다! 풀이는 약간의 수학..
백준 16214: N과 M https://www.acmicpc.net/problem/16214 16214번: N과 M 임의의 자연수 N과 M이 주어져 있다. A^B를 A의 B승이라고 할 때, 수열 N, N^N, N^(N^N), N^(N^(N^N)), ... 의 수들을 M으로 나눈 나머지는 수열의 어느 지점부터 항상 일정한 값을 가진다. N과 M이 주어져 있 www.acmicpc.net 일반적인 power tower 유형에서 모든 지수에 $N$을 넣어준 것이므로 난이도가 어떤 면에선 더 쉬워졌다고 볼 수 있습니다. 본문은 매우 훌륭한 자료인 https://rkm0959.tistory.com/181 을 인용했습니다. 위 글에 따르면 다음이 성립합니다. (Notation은 위 링크를 참조해주시기 바랍니다.) $$ [N,N,N, \cdo..
백준 17315번: Matrix Game (integer interpretation) https://www.acmicpc.net/problem/17315 17315번: Matrix Game The input will contain the six integers n, m, a, b, c, and d. www.acmicpc.net National Olympiad in Informatics, China, 2013, Day2에 Problem1로 출제된 문제라고 합니다. 행렬 거듭제곱 풀이에 대해 궁금하신 분은 이쪽 링크를 이용하시면 됩니다:Matrix Game (matrix interpretation) 정수 거듭제곱 풀이는 주어진 규칙대로 끝까지 전개하여 다음 식에서 $f$와 $g$를 구하는 것이 목표입니다. $$ F[n][m] = f(a,b,c,d) \times F[1][1] + g(a,b,c..

티스토리툴바