dp돌릴때

http://www.acmicpc.net/problem/2780

쉬운 dp문제인데, 아주 사소한 차이지만 실행시간을 확 줄일 수 있다

같은 dp를 돌리는데 여러개의 테스트케이스를 돌릴 경우,

매번 테스트케이스마다 dp를 계산하는게 아니라

아래처럼 맨 처음 dp쭉 돌리고 테스트케이스마다 이미 나온 결과를 그냥

참조하기만 하면 된다. 사소하지만 나중에는 큰차이가 될수도 있을 것 같다

#include #include using namespace std; int tc, N; int main(void){ // freopen("input.txt", "r", stdin); scanf("%d", &tc); int d[1005][10]; fill(d[1], d[1]+10, 1); for(int i=2; i<=1000; i++){ d[i][0] = (d[i-1][7])%1234567; d[i][1] = (d[i-1][2] + d[i-1][4])%1234567; d[i][2] = (d[i-1][1] + d[i-1][3] + d[i-1][5])%1234567; d[i][3] = (d[i-1][2] + d[i-1][6])%1234567; d[i][4] = (d[i-1][1] + d[i-1][5] + d[i-1][7])%1234567; d[i][5] = (d[i-1][2] + d[i-1][4] + d[i-1][6] + d[i-1][8])%1234567; d[i][6] = (d[i-1][3] + d[i-1][5] + d[i-1][9])%1234567; d[i][7] = (d[i-1][4] + d[i-1][8] + d[i-1][0])%1234567; d[i][8] = (d[i-1][5] + d[i-1][7] + d[i-1][9])%1234567; d[i][9] = (d[i-1][6] + d[i-1][8])%1234567; }while(tc--){ scanf("%d", &N); int sum = 0; for(int i=0; i< 10; i++) sum += d[N][i]; printf("%d\n", sum%1234567); } return 0; }