ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 11049
    알고리즘/acmicpc 2016. 7. 24. 12:14

    DP의 예시로 알고리즘 책에서 자주 나오는 유형


    DP는 배열의 인덱스 값을 얼마나 유용하게 잘 사용하느냐에 달려있는 것 같다.


    dp[FROM][TO] : FROM부터 TO까지의 행렬들을 곱할 때의 값


    위 값을 통해서 지속적으로 업데이트 해나가면 문제를 풀 수 있다.


     
    #include<cstdio>
    
    #define MAXN 500
    
    int dp[MAXN][MAXN];
    
    int data[MAXN][2];
    
    int main() {
    	int N;
    	int i, j, len;
    
    	freopen("input.txt", "r", stdin);
    	scanf("%d", &N);
    
    	for (i = 0; i < N; i++)
    		scanf("%d%d", &data[i][0], &data[i][1]);
    
    	for (len = 1; len < N; len++) {
    		for (i = 0; i + len < N; i++) {
    			for (j = i; j < i+len; j++) {
    				if (dp[i][i + len] == 0 ||
    					dp[i][i + len] > dp[i][j] + dp[j + 1][i + len] + data[i][0] * data[j + 1][0] * data[i + len][1])
    					dp[i][i + len] = dp[i][j] + dp[j + 1][i + len] + data[i][0] * data[j + 1][0] * data[i + len][1];
    			}
    		}
    	}
    
    	printf("%d\n", dp[0][N - 1]);
    
    	return 0;
    
    }
    

    '알고리즘 > acmicpc' 카테고리의 다른 글

    11437  (0) 2016.07.30
    2253  (0) 2016.07.24
    2229  (0) 2016.07.24
    4307  (0) 2015.10.17
    1577  (0) 2015.10.16

    댓글

Designed by Tistory.