RUN@KAIST 7/27 방학 연습 풀이

1. Vouchers

각각의 상자에 voucher의 번호를 적어놓은 후, 모든 배수를 순회하는 단순한 접근법으로 접근한다면, 쿼리당 O(n)의 시간이 걸리고 시간 초과가 날 것이다. 하지만, 에라토스테네스의 체만 생각해 봐도 줄일 여지가 충분하다. 모든 배수들을 열거하는 데 드는 시간은 O(n)이 아니라 O(n / a_i) 이기 때문이다. 고로 쿼리로 주어지는 모든 숫자가 다르기만 해도 O(nlgn) 시간 복잡도를 보장할 수 있다. O(n/1 + n/2 + n/3 + ... + n/n) = O(nlgn)이기 때문이다.

쿼리로 같은 숫자가 여럿 들어온다 하더라도 문제가 크게 달라지지 않는다. X번 쿼리로 가져간 최대 번호의 상자가 last_X번이라면, 다음 번에 볼 때 X ~ last_X 번의 상자들은 볼 필요 없다. 어차피 다 이전 쿼리에서 뽑아갔기 때문이다. 고로, naive한 접근법에다가. 이 last_X 위치를 관리해주기만 하면. O(nlgn) 정도 에 문제를 해결할 수 있다.

2. Teddies

전통적인 DP 문제인데 좀 귀찮다. 6중 루프의 압박을 느낄 수 있는 좋은(?) 문제이다.

먼저 3개 뭐시기 하는 조건이 없으면, (물론 이항계수로도 풀 수 있지만) DP[i][j][k][l] = (A1이 i개, A2가 j개, B1이 k개, B2가 l개 있을 때 늘어놓는 경우의 수) 라고 하면, 수열의 마지막 원소를 A1 / A2 / B1 / B2로 고정하는 식으로 점화식을 설계할 수 있다. 하지만 3개 뭐시기 하는 조건이 생겼으니, 인자 두개를 추가해야 한다. 나의 경우는 DP[i][j][k][l][next1][next2] = (A1이 i개, A2가 j개, B1이 k개, B2가 l개 있고, 수열을 전부 늘어놓은 후 뒤에 next1과 next2를 붙이고 싶을 때 늘어놓는 경우의 수) 와 같은 형태로 했다. 이럴 경우, 수열의 마지막 원소를 고정할 때 next1 / next2와 비교해서 올바르게 붙일 수 있는 원소인지를 확인할 수 있다. 답을 구하는 게 까다롭다고 생각할 수 있는데, next1 과 next2를 같은 걸로 줬다고 하면 (가령 A1), 마지막 원소는 B2밖에 못 오는데, 마지막에서 두 번째 원소는 아무거나 올 수 있다. 이런 식으로 next1과 next2가 같은 항에 대해서 다 더해 주면 답을 알 수 있다. 

여기까지는 좋은데 메모리 제한 이슈가 있다. 대략 160MB의 메모리를 소비하는데 문제의 128MB에 약간 못 미친다. (사실 원 문제는 32MB였는데 백준이라..) 이는 토글링이라는 잘 알려진 방법을 쓰면 되는데, DP[i] 라는 5차원 배열을 계산하기 위해서 필요한 것은 DP[i-1] 이라는 배열 뿐이다. DP[i-2] DP[i-3]에 뭐가 들어 있는지 전혀 상관 없다는 것이다. 고로 맨 첫 항을 40개를 잡을 필요 없이, 2개만 잡고, DP[i] 는 DP[i%2]에 덮어 쓰는 식으로 하면, 상태 전이를 완벽하게 구현하면서 메모리를 20배 줄일 수 있다. 널널하게 통과된다.

3. Captain Obvious and the Rabbit-Man

왜 정보 대회에 나왔는지 알 수 없는 문제이다. 풀이는 신기한데 일반인이 떠올릴 물건은 아닌 듯 하다. 놀랍게도 피보나치 수열과 전혀 상관없는 풀이를 사용한다.

다항식 P(x) = (x - F1)(x - F2)(x - F3) ... (x - Fk) 을 생각해 보자. 이 다항식을 전개해서 쓴 P(x) = x^k + a_1 * x^(k-1) + a_2 * x^(k-2) ... + a_n 이라는 식이 풀이의 핵심이다. (F1) = P(F2) = P(F3) = ... = P(Fk) 가 0인 것을 당연히 알 수 있는데, 이를 전개식에 대입하면 다음과 같이 풀어진다.

• P(1) = 1 + a_1 + a_2 + ... + a_n = 0 (F1 = 1)
• P(2) = 2^k + 2^(k-1) * a_1 + 2^(k-2) * a_2 + ... + a_n = 0 (F2 = 2)
• P(3) = 3^k + 3^(k-1) * a_1 + 3^(k-2) * a_2 + ... + a_n = 0 (F3 = 3)
• P(5) = 5^k + 5^(k-1) * a_1 + 5^(k-2) * a_2 + ... + a_n = 0 (F4 = 5)
• and so on..

이제 다항식에 대해서 생각하지 말고, a_1 .. a_n 이라는 수에 대해서만 생각하자. 어차피 저 수들은 N^2에 다항식 곱셈으로 계산할 수 있는 거니까 그렇게 생각해도 아무 문제가 없다. 우리가 알고 싶은 것은 p(k+1) 인데, 저 식과, a_1 .. a_n과, p(1) .. p(k) 만 가지고 p(k+1)을 알 수 있을까? 놀랍게도 그렇다.

• 1 + a_1 + a_2 + ... + a_n = 0 이다. 양변에 c_1 * 1을 곱하자. 
• 2^k + 2^(k-1) * a_1 + 2^(k-2) * a_2 + ... + a_n = 0 이다. 양변에 c_2 * 2를 곱하자.
• 3^k + 3^(k-1) * a_1 + 3^(k-2) * a_2 + ... + a_n = 0 이다. 양변에 c_3 * 3을 곱하자.
• 5^k + 5^(k-1) * a_1 + 5^(k-2) * a_2 + ... + a_n = 0 이다. 양변에 c_4 * 5를 곱하자.
• 계속 한 후, 더해보자.
• 지수승 k가 같은 애들로 묶어보자.
• ????

p(k + 1) = -p(k) * a_1 - p(k-1) * a_2 ... - p(1) * a_n 이라는 너무 깔끔한 identity로 식이 정리되어 버렸다. a_1 .. a_n을 N^2에 구했다면 식은 죽 먹기이다.