https://codeforces.com/contest/1498/problem/C
시간 1초, 메모리 256MB
input :
- t (1 ≤ t ≤ 100)
- n k (1 ≤ n,k ≤ 1000)
output :
- Output t integers, The i-th of them should be equal to the answer to the i-th test case.
i번째 테스트 케이스의 값이 i번째에 출력됩니다.
조건 :
-
A particle can pass through a plane directly, however, every plane produces an identical copy of the particle going in the opposite direction with a decay age k−1. If a particle has decay age equal to 1, it will NOT produce a copy.
하나의 입자는 평면을 지나갈 수 있다. 모든 평면은 k - 1의 값을 지닌 입자를 들어온 방향의 반대 방향으로 만든다. 만약 입자가 가진 값이 1인 경우에는 동일한 입자를 만들지 않는다. -
만들 수 있는 입자들의 개수를 출력하시오.
LeafSeek's 설명을 읽어보자.
풀이의 경우 3차원 dp를 사용해서 하지만 이를 이용하는 것보다 각 면에서 발생하는 입자들의 개수를 기록한다면 훨씬 편하지 않을 까 싶어 이해를 계속 못했다.
생각했던 것과 비슷한 설명이 있어 이를 통해 코드를 구현해 보았다.
결국 답에서 원하는 것은 마지막에 평면 바깥으로 나오는 입자들의 개수를 확인하는 것이다. 그렇기 때문에 평면에서 발생시키는 모든 입자들의 개수를 기록해야 한다.
그림에서 처럼 맨 처음에 5짜리 입자가 평면 5개에 들어간다고 생각할 때 첫 평면에서 반사되어 나오는 것 1개는 마지막에 더해 준다.
그리고 나서 각 평면에서 새로 만드는 입자들을 기록한다.
age 5
1 0 0 0 (각 평면에서 라기 보다는 평면과 평면 사이에 존재할 입자라고 생각을 하자)
age 4
1 1 1 1 (위에서 5짜리가 모든 평면을 돌면서 1개씩 만들것이기에 모두 1을 넣어준다.)
age 3
4 3 2 1 (모든 입자들이 축적되어 돌아온다. 이를 계산하기 위해서 reverse된 배열의 부분 합을 계산한다.)
age 2
4 7 9 10 (평면이 거울 처럼 반사시키기 때문에 이번에는 원상태의 배열의 부분 합을 계산한다.)
age 1
30 26 19 10 (이번에는 reverse된 배열)
그리고 이 값을 계속 ans에 저장을 한다.
마지막에 나온 값도 mod로 나눈 나머지를 얻어야 한다는 것을 기억해야 한다.
import sys
mod = int(10 ** 9 + 7)
for _ in range(int(sys.stdin.readline())):
n, k = map(int, sys.stdin.readline().split())
if k == 1:
print(1)
continue
if n == 1:
print(2)
continue
now = [0] * (n - 1)
now[0], ans, direction = 1, 0, 1
for i in range(k):
temp, total = [0] * (n - 1), 0
# from left to right
if direction == 1:
for j in range(n - 1):
total += now[j] % mod
temp[j] = total
direction = -direction
else:
for j in range(n - 2, -1, -1):
total += now[j] % mod
temp[j] = total
direction = -direction
now = temp
ans += total
print((ans + 1) % mod)
