th3_b3st_h4ck3r

dp[i] = 1 * dp[i - 1] + 2 * dp[i - 2] + 3 * dp[i - 3] ... dp[i - K] 위와 같은 점화식으로 dp[N]를 구해야 한다고 생각해보자. 일단 dp를 하나하나 구한다고 하면 총 O(NK)의 시간복잡도가 나올 것이다. 그러나 이를 잘 최적화하면 O(K^3 log N) 안에 dp[N]을 구할 수 있다. 바로 행렬 거듭제곱을 이용하는 것인데, 그 전에 "행렬 곱셈을 한다"가 어떤 의미인지 한 번 해석을 해보도록 하겠다. 다음과 같은 행렬 두 개가 있다고 가정하자. [1, 2, 3] [10] [1, 0, 0] [20] [0, 1, 0] [30] 그리고 위 행렬을 곱하면, 다음과 같은 행렬이 나올 것이다. [1*10+2*20+3*30 = 140] [1*10+0*20+0..

- 1번 문제 일단 A가 C보다 순위가 낮으므로, A 9 ... 6 -> 6 ... 14 -> 11 -> 8 -> 14 ... 이런 식으로 모든 사이클을 구해보았다. 위 사이클에선 반복 주기를 찾을 수 있는데, 첫 번째 사이클은 4, 두 번째는 5, 세 번째는 2, 네 번째는 1, 다섯 번째는 3이다. 이런 정보와 최소공배수 개념을 이용해 a^m이 되기 위해 a를 몇 번 제곱해야 하는지 알아낼 수 있다. 일단 (a^m)[1]=2이므로, 첫 번째 사이클은 총 2+4k번 반복됐다는 걸 알 수 있다. 따라서 m은 3, 7, 11, 15, 19 ... 중 하나가 될 수 있다. 다음으로 (a^m)[3]=15이므로, 두 번째 사이클은 총 0+5k번 반복됐다는 걸 알 수 있다. 따라서 m은 1, 6, 11, 16, ..

A197. 실수 전체의 집합 U의 두 부분집합 A, B에 대하여 n(A) = 5, B={ ( x + a ) / 2 | x ∈ A}이다. 두 집합 A, B가 다음 조건을 만족시킬 때, 상수 a의 값을 구하시오. (4점) (가) 집합 A의 모든 원소의 합은 28이다. (나) 집합 A ∪ B의 모든 원소의 합은 49이다. (다) A ∩ B = {10, 13} 이 문제는 1등급 킬러 태그가 붙어있는 문제였지만 제일 쉬웠다. 일단 집합 A의 원소의 개수가 주어졌으므로 A를 {a1, a2, a3, a4, a5}의 집합으로 나타내봤다. 이렇게 나타냈더니 조건 (가)로 인해 a1+a2+a3+a4+a5 = 28이라는 수식을 사용할 수 있게 되었다. 그 이후, 문제에 나와있는대로, 집합 B를 { ( a1 + a ) / 2..

A191. 어느 고등학교 학생들을 대상으로 수학문제 A, B, C의 구매 여부에 대하여 조사한 결과가 다음과 같다. (가) A와 B를 모두 구매한 학생은 15명, B와 C를 모두 구매항 학생은 12명, C와 A를 모두 구매한 학생은 11명이다. (나) A와 B 중 적어도 하나를 구매한 학생은 55명, B와 C 중 적어도 하나를 구매한 학생은 54명, C와 A 중 적어도 하나를 구매한 학생은 51명이다. 수학 문제집 A를 구매한 학생의 수를 구하시오. (4.1점) 자이스토리 1등급 문제 치고 쉬운 문제였다. 일단 이 문제를 머리로 생각하며 풀긴 어려우니 벤다이어 그램을 통해 한눈에 보기 쉽게 나타내보았다. 이렇게 나타낸 상태에서 각 영역에 고유한 이름을 붙이고 보기의 (가) 조건을 이용해 수를 나타내보았다..