acmicpc.net 1416 - 팬 서비스

팬 서비스

채점: http://www.acmicpc.net/problem/1416

길이가 2 * K인 티켓이 있는데, 이 티켓이 다음 두 조건중 하나를 만족하면 당첨 티켓이라고 한다:

1. 앞쪽 K자리의 각 자리 수의 합(e.g.123 -> 1+2+3)이 뒤쪽 K자리의 것과 같다.

2. 홀수 번째 인덱스(1, 3, ...)의 각 자리 수의 합과 짝수 번째 인덱스(0, 2, ...)의 각 자리 수의 합이 같다.

티켓 절반의 길이 K와 티켓에 사용되는 숫자 목록이 주어질 때, 당첨 티켓이 몇 가지인지 구하라(modulo 999983).

(생각해보니까.. 엄청 간단한 문제였는데, 너무 단순하게 생각해서 많은 TLE를 겪었다 ㅜㅜ)

간단하게 생각하면, 이 문제의 답을 세는 것은 다음과 같이 할 수 있습니다:

(1번 조건을 만족하는 티켓의 개수) + (2번 조건을 만족하는 티켓의 개수) - (1번과 2번을 모두 만족하는 티켓의 개수)

일단 가장 단순하게 3차원 동적계획법을 생각해봅시다: d[길이][합][짝수번째와 홀수번째 합의 차이]

이렇게 하면, 1번 조건을 만족하는 티켓의 개수는 

로 셀 수 있고, 2번 조건을 만족하는 티켓의 개수는

와 같이 셀수 있으며, 두 조건을 모두 만족하는 티켓의 개수는

와 같이 셀 수 있습니다. 참 쉽죠?

다만.. 이 방법은 TLE를 피하기가 참 어렵다는 문제점을 갖고있습니다.

이 문제를 시간 안에 풀기 위해 d배열을 2차원으로 바꿔봅시다:

d[길이][합].

이렇게 하더라도 우리는 답을 구할 수 있습니다.

지금까지는 이렇게 절반씩 자르는것만 생각했는데,

이렇게 홀수와 짝수를 나눠서 생각해도 되거든요.

이렇게 생각하면,

1번 조건을 만족하는 티켓의 개수는

이렇게 간단하게 셀수 있고(첫번째 그림을 생각해보면 쉽죠?)

놀랍게도 2번 조건을 만족하는 티켓의 개수도

이렇게 간단하게 셀 수 있습니다(두 번째 그림에서 윗 줄은 짝, 아래 줄은 홀수로 생각해보세요)

그리고 대망의 1번과 2번을 모두 만족하는 티켓의 개수도

이렇게 간단하게 셀 수 있습니다!

이렇게 하면 복잡도가 엄청나게 줄어들기때문에 더이상 TLE를 걱정하지 않아도 됩니다.

재미있죠?ㅎㅎ

이렇게 약간만 더 생각하면 복잡도를 엄청나게 줄일 수 있는 경우가 참 많은데,

역시 ICPC공부에는 끈질기게 생각하는게 가장 중요한것 같습니다.