정말로 그간 격조했다. 반쯤 블로그를 유기한 것 같은데... 현생이 너무 바빴다. 방학 때 이 블로그를 조금 더 많이 충실하게 만들 생각이다. 이번 문제는 ICPC 북서유럽 리저널인 SWERC 2015 C번 문제다. 서강대학교 PS 학회와 연합 팀연습을 했을 때 다 같이 시원하게 말린 다음 내 아이디어로 푼 문제다. (자랑 맞다.) 발상의 전환이 필요한 문제다. 이런 문제가 아니었으면 내 아이디어가 튀어나오기 전에 괴물 팀원이 구현을 끝내 놓으신다. 나는 우리 동아리 코딩 최약체다. ICPC 리저널답게 영어로 된 문제다. 처음에는 내가 직접 번역하다가 영 귀찮아서 DeepL의 초고를 보고 내가 덧대는 방식으로 번역하기로 했다. 난 영어도 잘 못하는데... 그럼 본격적으로 풀이에 돌입해 보자. 문제 Aft..

분할 정복은 어떤 수의 거듭제곱만을 대상으로 하는 것이 아니다. 오히려 어떤 수의 거듭제곱보다는 행렬을 거듭제곱하는 것을 더욱 많이 볼 수 있다. 선형 점화식으로 주어진 수열일 경우 행렬을 거듭제곱함으로서 손 쉽게, 다이나믹 프로그래밍보다 훨씬 효율적으로, 매우 큰 n에 대하여 값을 구할 수 있다. 그럼 본격적으로 풀이에 돌입해 보자. 지문은 영어 한 줄, 해석 한 줄 번갈아서 표시된다. 문제 In the Fibonacci integer sequence, \(F_0 = 0, F_1 = 1\), and \(F_n = F_{n−1} + F_{n−2}\) for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are: 0, 1, 1, 2, ..