글 읽기 - 반례를 주시거나, 틀린 점을 알려주세요.

math_rabbit_1028 4년 전 0

dp와 quick sort를 이용해서 풀었는데 뭐가 잘못되었는지 모르겠네요

참고로 정렬한 이유는 높이가 큰 곳부터 네 방향을 탐색하기 위해서입니다. 네 방향의 높이가 자기 자신보다 크면 dp값에 더하게 했는데 높이가 높은 곳부터 해야지 될 것 같아서요.

(사실 quick sort를 처음 해봐서 인터넷에서 찾아서 해 봤는데 맞는지도 모르겠네요.)

//1520 - 내리막 길
#include <iostream>
using namespace std;
int n, m, map[550][550], dp[550][550], arr[3][300000], r = 0;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

void swap(int* x, int* y) {
	int temp;
	temp = *x;
	*x = *y;
	*y = temp;
}

//quickSort : 내림차순(높이가 높은 것부터 하기 위해서)
void quickSort(int left, int right, int* data) {
	int pivot = (left + right) / 2;
	int j = pivot;
	if (left < right) {
		for (int i = left; i < pivot; i++) {
			if (data[pivot] > data[i]) {
				j--;
				swap(&data[i], &data[j]);
				swap(&arr[1][i], &arr[1][j]);
				swap(&arr[2][i], &arr[2][j]);
			}
		}
		if (data[pivot] > data[j]) {
			swap(&data[pivot], &data[j]);
			swap(&arr[1][pivot], &arr[1][j]);
			swap(&arr[2][pivot], &arr[2][j]);
		}
		pivot = j;

		for (int i = j + 1; i <= right; i++) {
			if (data[pivot] < data[i]) {
				j++;
				swap(&data[i], &data[j]);
				swap(&arr[1][i], &arr[1][j]);
				swap(&arr[2][i], &arr[2][j]);
			}
		}
		if (data[pivot] < data[j]) {
			swap(&data[pivot], &data[j]);
			swap(&arr[1][pivot], &arr[1][j]);
			swap(&arr[2][pivot], &arr[2][j]);
		}
		pivot = j;
		quickSort(left, pivot - 1, data);
		quickSort(pivot + 1, right, data);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> map[i][j];
			arr[0][++r] = map[i][j];
			arr[1][r] = i;
			arr[2][r] = j;
		}
	}
	quickSort(1, r, arr[0]);
	dp[1][1] = 1;
	for (int i = 1; i <= n * m; i++) {
		for (int j = 0; j < 4; j++) {
			int x = arr[1][i] + dx[j], y = arr[2][i] + dy[j];
			if (1 <= x && x <= n && 1 <= y && y <= m)
				if (map[arr[1][i]][arr[2][i]] < map[x][y])
					dp[arr[1][i]][arr[2][i]] += dp[x][y];
		}
	}
	cout << dp[n][m] << "\n";
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 주시거나, 틀린 점을 알려주세요.

math_rabbit_1028 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말