ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1937
    알고리즘/acmicpc 2016. 9. 6. 18:50

    모든 경로를 탐색하려고 하면 경우의 수가 무척 많아져서 어렵다. 여기서는 문제의 조건을 잘 살펴야 한다.


    - 판다는 상,하,좌,우 중 하나의 경로로 이동한다

    - 대나무의 양은 증가하는 순서여야 한다.


    위 두가지 조건만을 이용해서 dp를 만들어 줄 수 있다.


    dp[x][y]는 어떤 위치(x,y)로 도달 할 때 판다가 최대 살 수 있는 일 수를 가지고 있다고 하자.


    그럼 다음과 같은 점화식을 적용 할 수 있다.


    dp[x][y] = (상하좌우에 있는 대나무중 현재 위치의 대나무보다 양이 작은 값들의 dp중 가장 큰 것) + 1


    이해를 돕기 위해 그림으로 부연 설명을 하면..

    파란색으로 칠해둔 위치의 dp값을 업데이트 하려고 한다. 이때 파란색 위치로 접근 할 수 있는 경로는 (x,y)위치의 상하좌우중 (x,y)의 위치보다 대나무 수가 적은 곳(상, 우)이다. 상, 우의 dp값중 가장 큰 값(2)에서 하루를 더 살 수 있는 것으로 (x,y)의 위치에 도달 할 때는 판다는 최대 3일을 살 수 있다.


    위 알고리즘을 적용하려면 대나무의 수가 적은 순서대로 탐색을 해야한다. 그렇지 않으면 중간에 누락되는 경로가 생길 수 있다.


    반드시 대나무가 증가하는 순서대로 진행되므로 circle이 생기지 않기 때문에 위 알고리즘 만으로 모든 경우를 포함 할 수 있다.


     
    #include<cstdio>
    #include<algorithm>
    
    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    
    using namespace std;
    
    struct Node {
    	int val, r, c;
    };
    
    int map[505][505];
    int dp[505][505];
    
    Node node[500 * 500];
    
    int dr[4] = { 0, 1, 0, -1 };
    int dc[4] = { 1, 0, -1, 0 };
    
    bool compare(Node a, Node b) {
    	if (a.val < b.val)
    		return true;
    	return false;
    }
    
    int main() {
    	int N, i, j, nr;
    	int r, c, val, ans;
    
    	scanf("%d", &N);
    
    	nr = 0;
    	for (i = 1; i <= N; i++){
    		for (j = 1; j <= N; j++) {
    			scanf("%d", &map[i][j]);
    			node[nr].r = i;
    			node[nr].c = j;
    			node[nr++].val = map[i][j];
    		}
    	}
    
    	sort(&node[0], &node[nr], compare);
    	ans = 0;
    
    	for (int i = 0; i < nr; i++) {
    		r = node[i].r, c = node[i].c, val = node[i].val;
    
    		dp[r][c] = 1;
    		for (int j = 0; j < 4; j++) {
    			if (map[r][c] > map[r + dr[j]][c + dc[j]]) {
    				dp[r][c] = MAX(dp[r][c], dp[r + dr[j]][c + dc[j]] + 1);
    				ans = MAX(ans, dp[r][c]);
    			}
    		}
    	}
    
    	printf("%d\n", ans);
    
    	return 0;
    }
    

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

    SW 역량테스트 기출 문제집 분석  (4) 2017.04.21
    10422  (0) 2017.04.05
    4095  (0) 2016.08.15
    11437  (0) 2016.07.30
    2253  (0) 2016.07.24

    댓글

Designed by Tistory.