n=10, m=2000의 제한이 주어진다.
예제를 보면서 생각해보니 일단 떠오르는 것은
d[x][y] : x번째 수를 y로 결정했을 때, 만들 수 있는 경우의 수
d[x][y] = sum(ny=2y ~ m, d[x+1][ny]) 가 될 것이고,
답은 sum(y=1~m, d[1][y]) ...
한 번 d[x][y]에 관한 식을 조금 변형해보자.
d[x][y] : x번째 수를 y로 결정했을 때, x번째까지 만들 수 있는 경우의 수
d[x][y] = sum(ny=1 ~ y/2, d[x-1][ny]) 으로 변형하고 for loop dp로 구현해보자.
답은 sum(y=1~m, d[n][y])...가 될 것 같은데, 어라? O(N*M*M)만에 해결될 것 같다.
답을 구할 때의 m번은 따로 처리되기 때문이다...음 그렇게 치면 memoization이 있기 때문에 위의 top-down방식에서도 O(N*M*M)만에 해결될 것 같아 보인다.
먼저 bottom-up방식으로 구현해보고, top-down으로도 구현해 봐야겠다.
일단 bottom-up방식으로 구현했는데 시간 초과를 받았다... O(N*M*M)이라도, T값, 즉 테스트 케이스의 개수가 많으면 시간초과가 날 것이다. 음 근데 문득 떠오른 것이... d배열은 다른 테스트 케이스에도 사용가능 하지 않을까?
그렇다. x번째 수를 y로 결정했을 때, x번째까지 만들 수 있는 경우의 수이기 때문에... 일단 d배열을 다 구해놓고, 각 테스트케이스에 대해서 sum(y=1 ~ m, d[n][y])만 구하면 되는 것이다.
그렇게 제출해보니, 시간초과는 사라지고 WA를 받았다. 예제로 10, 2000을 넣어보니 음수가 나온다. integer overflow일 것이다. long long형으로 수정해서 제출해 봐야겠다.
AC를 받았다. 12ms로 통과했는데, 0ms인 사람들도 꽤 보인다.
bottom up 구현에서 d[x][y]를 구할 때, ny=1 ~ y/2까지의 d[x-1][ny]의 합을 구하는데, 이 부분에서 시간 단축을 할 수 있어 보인다. 바로 부분합(누적합)을 이용하는 것이다. d[x-1][y]값들을 구할때, d[x-1][~]의 부분합(누적합)을 미리 구해놓고, d[x][~]를 구할 때, 이용하면 O(m)의 시간을 O(1)로 단축시킬 수 있다. 즉 전체 수행시간을 O(N*M)으로 단축시킬 수 있는 것이다.
결국 0ms로 AC를 받았다!
다른 분들의 코드를 보고 있는데, 음 정말 대단하신 것 같다. 다들... 내가 정말 허접해보인다. 인상깊은 구현을 여기 써보고 그렇게도 풀어봐야겠다.
d[x][y] : x번째 수를 y로 결정했을 때, 만들 수 있는 경우의 수 <- 내가 한 방법.
d[x][y]는 같은데, 고수분들의 d[x][y]는 의미가 좀 다르고 그렇기에 식도 다르게 나온다.
나처럼 시간을 단축시키기 위해 누적합을 쓸 필요도 없다.
d[x][y] = 1부터 y까지의 수 중에서 x개의 수를 고르는 경우의 수 <- 바로 답 그 자체이다.
점화식이 중요한데... 알고보면 이미 다른 문제들에서도 몇 번 봤던 방식으로 생각하는 것인데, 난 전혀 생각하지 못했다.
d[x][y] = d[x][y-1] + d[x-1][y/2] 이다!
바로 1부터 y까지의 수 중에서 y를 고를지 말지 결정하는 것이다.
y를 고르지 않는다면 1부터 y-1까지의 수 중에서 x개를 고르는 경우가 될 것이고
y를 고른다면 1부터 y/2까지의 수 중에서 x-1개를 고르는 경우가 될 것이다!
이렇게 하면 모든 경우도 커버할 뿐 아니라, O(N*M)만에 가능하다. 정말 아름다운데... 난 생각을 못했다. 좋은 문제다.
한 번 이 방식을 이용해서 top-down으로 풀어봐야겠다. 기저 사례의 경우 dp(n, m)에서
n < m인 경우는 0을 return하고, n==1인 경우는 m을 return했다. 확실히 이 방식이 top-down으로 하든 bottom-up으로 하든 쉬울 것이다.
댓글 없음:
댓글 쓰기