ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2229
    알고리즘/acmicpc 2016. 7. 24. 11:38

    나이순으로 정렬이 이미 되었으니 해야 할 일은 여기서 연속된 배열을 어떻게 여러개로 나눠서 최대의 점수를 내는 조를 만드느냐이다.

    (문제가 나이 정렬을 해주지 않고 냈으면 더 어려울 뻔 했는데 친절하게 나이 정렬을 해준 뒤에 문제를 풀라고 했다)


    위 문제는 DP로 풀 수 있다. 먼저 다음과 같은 배열을 선언한다


    dp[FROM][TO] : FROM학생부터 TO학생까지 조를 짤 때의 최대의 점수가 나오는 경우

    목표는 FROM, TO까지 무조건 최대의 점수를 가지는 것이며 어떻게 분할 되는지는 상관하지 않는다


    FROM에서 TO까지의 범위를 차근차근 늘려서 1번 학생부터 N번 학생가지 포함되는 경우까지 만들어준다.


     
    #include<cstdio>
    
    #define MAXN 1000
    
    #define MAX(A, B) ((A) > (B) ? (A) : (B))
    #define MIN(A, B) ((A) < (B) ? (A) : (B))
    #define INF 10005
    
    
    int dp[MAXN + 5][MAXN + 5];
    
    int arr[MAXN + 5];
    
    int main() {
    	int N, i, j, len;
    
    	int _min, _max;
    
    	freopen("input.txt", "r", stdin);
    	scanf("%d", &N);
    
    	for (i = 0; i < N; i++)
    		scanf("%d", &arr[i]);
    
    	for (len = 0; len < N; len++) {
    		for (i = 0; i + len < N; i++) {
    			_min = INF, _max = 0;
    
    			for (j = i; j <= i + len; j++) {
    				_min = MIN(_min, arr[j]);
    				_max = MAX(_max, arr[j]);
    
    				dp[i][i + len] = MAX(dp[i][j] + dp[j + 1][i + len], dp[i][i+len]);
    			}
    
    			dp[i][i + len] = MAX(_max - _min, dp[i][i + len]);
    		}
    	}
    
    	printf("%d\n", dp[0][N - 1]);
    
    	return 0;
    }
    

    하지만 위 방법은 O(N^3)이다. 2초 제한시간에 아슬아슬하게 통과했지만(772ms) 원칙상으로는 통과해선 안된다.
    다른 사람들의 코드를 봤는데 상위랭크는 대부분 O(N^2)로 풀었다.

    나와 푼 방식의 개념은 기본적으로 비슷하나 이분들은 FROM은 어차피 1이 될 것이기 때문에 이 경우를 무시하고 dp[TO]만 가지고 풀었다.

    새로운 dp[TO]를 만들기 위해 TO' < TO에서 dp[TO'] + (TO'+1 부터 TO 까지 조를 짤 경우)에 대한 최대값을 계속 업데이트 해줬다.

    내 방법보다 한 번 더 추상화해서 문제에 접근한 방식이다.

    정말 고수는 다르구나 하는 생각이 들었다.


     
        dp[1] = fabs(arr[1]-arr[0]);
        for(int i=2; i<n; i++)
        {
            maxnum=minnum=arr[i];
            for(int j=i; j>0; j--)
            {
                maxnum = max(maxnum, arr[j]);
                minnum = min(minnum, arr[j]);
                dp[i] = max(dp[i], maxnum-minnum+dp[j-1]);
            }
        }
        printf("%d", dp[n-1]);

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

    2253  (0) 2016.07.24
    11049  (0) 2016.07.24
    4307  (0) 2015.10.17
    1577  (0) 2015.10.16
    1946  (0) 2015.10.16

    댓글

Designed by Tistory.