글 읽기 - bottom-up 방식 반례 부탁드립니다.

tngus1140 2년 전 0

top-down으로는 통과했고 bottom-up 방식도 될 것 같아 시도해보고 있습니다.

bottom-up으로 진행하다 아직 구하지못한 위치가 나오면 해당 위치 값을 top-down으로 구하는 방식입니다.

bottom-up으로 풀려다보니 어렵네요...

어떤 반례가 있을까요..?

#include <iostream>

using namespace std;

int matrix[501][501], M, N;
int dp[501][501];
const int mX[4]{ -1,1,0,0 };
const int mY[4]{ 0,0,-1,1 };

// 주변을 이동하여 계산한 곳을 찾는다.
int solve_recur(int x, int y) {
	if (dp[y][x] != -1)return dp[y][x];

	int fX, fY;

	for (int i = 0; i < 4; i++) {
		fX = x + mX[i];
		fY = y + mY[i];
		if (fX == 0 || fY == 0 || fX > N || fY > M)continue;
		if (matrix[y][x] >= matrix[fY][fX])continue;

		dp[y][x] = max(dp[y][x], solve_recur(fX, fY));
	}

	if (dp[y][x] == -1)dp[y][x] = 0;
	return dp[y][x];
}

int solve_bottomUp() {
	for (int y = 1; y <= M; y++) {
		for (int x = 1; x <= N; x++) {
			if (x == 1 && y == 1)continue;
			if (dp[y][x] != -1)continue;

			int pX, pY, cost = 0;
			for (int k = 0; k < 4; k++) {
				pX = x + mX[k];
				pY = y + mY[k];

				if (pX == 0 || pY == 0 || pX > N || pY > M)continue;
				if (matrix[y][x] >= matrix[pY][pX])continue;
				
				if (dp[pY][pX] != -1) {
					cost += dp[pY][pX];
				}
				else {
					cost += solve_recur(pX, pY);
				}
			}

			dp[y][x] = cost;
		}
	}

	return dp[M][N];
}

int main()
{
	cin.sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> M >> N;
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> matrix[i][j];
			dp[i][j] = -1;
		}
	}

	dp[1][1] = 1;

	cout << solve_bottomUp();
	return 0;
}

doju 2년 전 1

틀리는 이유는 bottom-up 방식과는 별 관련이 없습니다. solve_recur()이 계산하고 있는 값을 다시 확인해 보세요.

여담으로 이 풀이는 bottom-up 방식이라고 할 수 없습니다. Bottom-up 방식의 핵심은 항을 계산하는 순서를 잘 설계하여 43번째 줄과 같이 점화식에 필요한 항이 아직 계산되어 있지 않은 상황이 애초에 발생하지 않도록 하는 것입니다. 이 문제를 온전히 bottom-up 방식으로 해결하는 것은 top-down 방식에 비해 꽤 어렵습니다.

3
4 1
3 2

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

문제

문제

출처

ICPC

bottom-up 방식 반례 부탁드립니다.

tngus1140 2년 전 0

doju 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말