오늘의 PS (3) - 220420

카테고리 제목이 PS인데 너무 CP만 다룬 것 같아서 최근에 푼 백준 문제들 중 인상깊었던 것들을 정리해서 쓰려고 한다. 세미나를 준비하면서 백준에 있는 행렬 DP 문제는 거의 몽땅 푼 것 같다.. 이번에 정리할 문제들도 모두 여기에 속하는 것들이다.

 

2086 - 피보나치 수의 합, 11440 - 피보나치 수의 제곱의 합, 11778 - 피보나치 수와 최대공약수

모종의 정리들을 알거나 규칙을 찾으면 평범한 피보나치 수 문제로 환원할 수 있다. 2086은 규칙을 찾아서 풀었고, 뒤의 두 개는 적당히 검색해서 풀었다.

 

17401 - 일하는 세포

보자마자 풀이는 보이는데, 구현이 좀 귀찮은 문제이다. 신경써야 할 점은

1. 같은 행렬을 거듭제곱하는 문제들과는 다르게 교환법칙이 통하지 않는다.

2. 주어진 행렬들을 Prefix Sum 느낌으로 앞에서부터 곱해서 가지고 있어야 한다.

3. \(D\)를 \(T\)로 나누어 잘 처리해주어야 한다.

이 정도를 생각하고 들어가면 구현이 크게 어렵지는 않을 것이다.

 

21071 - Long Grid Covering

3*N의 격자를 트리오미노로 채우는 경우의 수를 구하는 문제이다.

잘 그려보면 점화식은 \(A_{i} = A_{i-1} + 3A_{i-2} + 5A_{i-3} + 2A_{i-4} + 2A_{i-5} + 4A_{i-6} .. \)임을 알 수 있고, (이후는 2, 2, 4 반복이다.) \(A_{i}\)에서 \(A_{i-3}\)을 빼주면 선형 점화식을 구할 수 있다. 이후는 평범한 행렬 거듭제곱 문제가 된다.

 

1492 - 합

이항 정리를 사용하면, \( (n+1)^k = \sum_{i=1}^k  {_{k}}{C_{i}} n^{i} \) 임을 알 수 있다. 이는 일종의 선형 점화식이므로, \(O(K^2)\)으로 조합 값을 전처리해준 후 행렬마다 \(N^0, N^1, .. N^k, S_N\)을 들고 있는다고 생각하면 문제를 해결할 수 있다.

 

13716 - 피보나치 수열처럼 보이지만...

식 정리를 잘 해주면, 답은 \(a_{n}F_{n} + a_{n-1}F_{n+1}\)이라는 것을 알 수 있다. 여기서 \(a_i\)는 \(a_{0} = 0, a{1} = 1, a_{i} = i^k - a_{i-1} + a_{i-2} \)와 같이 정의되는 수열이다. 이는 1492와 비슷한 방법을 사용하면 구할 수 있으므로, 문제를 해결할 수 있다.

 

여담으로, 기여할 때 보니 (어떤 문제던간에) 벌레캠프로 푼 사람들이 꽤 보이더라. 공부를 안 해 놨었는데, 편해 보이길래 배울까 고민 중이다.