ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2253
    알고리즘/acmicpc 2016. 7. 24. 13:10

    위 문제는 가속/감속을 최대 1 만큼 한다는 것에 힌트가 있다.


    돌의 개수가 최대 10000개 일 때 최대로 낼 수 있는 속도는 142이다. K*(K+1)/2 < 10000

    현재 위치의 돌과 돌에 도착할 때의 속도로 새롭게 정점을 표현한다면 최대 정점의 개수는 10000 * 142 로 배열 내에서 선언이 가능한 범위가 된다.


    dp[N][V] : N번째 돌에 V번째 속도로 도착할 때의 최소 점프횟수


    이제 각각의 정점을 방문해서 다음 위치에 움직일 때 최소 횟수로 움직이는 값을 업데이트 해주면 된다.


     
    #include<cstdio>
    
    #define MAXN 10000
    
    int dp[MAXN + 5][200];
    int forbid[MAXN];
    
    int main() {
    	int N, M;
    	int i, j, tmp;
    
    	int ans;
    
    	freopen("input.txt", "r", stdin);
    	scanf("%d%d", &N, &M);
    
    	while (M--) {
    		scanf("%d", &tmp);
    		forbid[tmp] = 1;
    	}
    
    	dp[1][0] = 1;
    
    	for (i = 1; i <= N; i++) {
    		if (forbid[i])
    			continue;
    		for (j = 0; j < 200; j++) {
    			if (dp[i][j]) {
    				if (i + j <= N) {
    					if (dp[i + j][j] == 0 || dp[i + j][j] > dp[i][j] + 1)
    						dp[i + j][j] = dp[i][j] + 1;
    				}
    				if (i + j + 1 <= N) {
    					if (dp[i + j + 1][j + 1] == 0 || dp[i + j + 1][j + 1] > dp[i][j] + 1)
    						dp[i + j + 1][j + 1] = dp[i][j] + 1;
    				}
    				if (j - 1 > 0 && i + j - 1 <= N) {
    					if (dp[i + j - 1][j - 1] == 0 || dp[i + j - 1][j - 1] > dp[i][j] + 1)
    						dp[i + j - 1][j - 1] = dp[i][j] + 1;
    				}
    			}
    		}
    	}
    
    	ans = 0;
    
    	for (i = 0; i < 200; i++) {
    		if (dp[N][i] != 0)
    			if(ans == 0 || ans!=0 && dp[N][i] < ans)
    				ans = dp[N][i];
    	}
    		
    	printf("%d\n", ans - 1);
    
    	return 0;
    
    }
    

    문제에서 제시한 정점에서 벗어나 새로운 정점을 만들어주는 방식이 중요하다. DP문제를 풀 때는 위 방식이 핵심이다.


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

    4095  (0) 2016.08.15
    11437  (0) 2016.07.30
    11049  (0) 2016.07.24
    2229  (0) 2016.07.24
    4307  (0) 2015.10.17

    댓글

Designed by Tistory.