전체 글 (117) 썸네일형 리스트형 백준 27435번: 파도반 수열 2 https://www.acmicpc.net/problem/27435 27435번: 파도반 수열 2 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ T ≤ 1,000, 1 ≤ N ≤ 1018) www.acmicpc.net 파도반 수열의 초반 항이 10개 주어져있고, 그림도 친절하게 주어져있어 점화식을 추론하기 쉽습니다. $$P(n) = P(n-1) + P(n-5)$$ 이 점화식에 따르면 $5 \times 5$ 행렬 거듭제곱을 통해 빠르게 답을 구할 수 있게 됩니다. $$ \begin{bmatrix} P(n+4) \\ P(n+3) \\ P(n+2) \\ P(n+1) \\ P(n) \end{bmatrix} = \begin{bmatrix} 1.. 백준 18151번: DivModulo https://www.acmicpc.net/problem/18151 18151번: DivModulo Modulo (mod) is a very common operator on integers. For two integers n and d with d > 0, r ≡ (n mod d) is defined where 0 ≤ r < d and there exists an integer q, such that n = q × d+r. For example, (200 mod 5) ≡ 0 means that the remainder of 200 divi www.acmicpc.net 정수론에 대한 지식이 부족한 저로서는 매우 힘든 문제 중 하나였습니다. 처음에는 Lucas' Theorem과, Andrew Granvil.. 백준 10909번: Quaternion inverse https://www.acmicpc.net/problem/10909 10909번: Quaternion inverse 각 \(A\)가 주어질 때마다, \(AB = 1\)을 만족하는 \(B = a + bi + cj + dk\)들 중 하나를 나타내는 네 개의 정수 \(a\), \(b\), \(c\), \(d\)를 공백으로 구분하여 \(T\) 줄에 걸쳐 출력하면 된다. 만약 이런 \(B\)가 www.acmicpc.net 사원수, quaternion이라는 낯선 대상이 주어졌을 뿐, 실제로는 복소수의 역원을 구하는 것과 크게 다르지 않습니다. 일반적인 사원수에 대해 역수를 구하는 방법은 다음 링크 와 같이 주어집니다. 다시 말하면, 다음 식이 성립합니다. $$ \times < a-bi-c.. 백준 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, .. 백준 3752번: 최대공약수 행렬식 https://www.acmicpc.net/problem/3752 3752번: 최대공약수 행렬식 집합 S = {x1, x2, ..., xn}가 인수에 대해서 닫혀있으려면, 모든 xi ∈ S에 대해서, xi의 모든 약수 d는 d ∈ S를 만족해야 한다. 인수에 대해 닫힌 집합 S를 최대공약수 행렬 (S) = (sij), sij = GCD(xi,xj)로 만 www.acmicpc.net 수학적으로는 어렵지만 코딩은 쉬운 문제입니다. Zhongshan Li의 1990년 paper 을 보면, 3752번에서 쓰는 모든 표현이 그대로 나오고 있습니다. 즉 $$\textrm{det} [S] = \prod_{x \in S} \phi (x)$$ 이것을 그대로 구현하면 정답을 받습니다. Totient Function의 구현.. 백준 11500번: Polynomial https://www.acmicpc.net/problem/11500 11500번: Polynomial A polynomial \(f(k)\) of degree \(t\) with integral coefficients is given as \(f(k) = c_0 + c_1k + c_2k^2 + \cdots + c_tk^t\), where the coefficients \(c_0, \dots, c_t\) are all integers. Here, we are interested in the sum \(S(n)\) of \(f(0)\), \(f(1)\), . www.acmicpc.net 전처리를 하면 쉬운데, 전처리 없이는 다소 복잡한 문제가 될 수 있을 것 같습니다. 일단 문제를 풀기 위해 주어진 식을 그.. 백준 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.. 이전 1 2 3 4 5 6 7 ··· 15 다음 목록 더보기