글 읽기 - 반례 알려주세요!

oh20020409 2년 전 0

arr[i] : i 번째에 사용할 벽장의 값

dp[i][j][k]의 정의 : i 번째에 비워야하는 두 개의 벽장의 위치 j,k 일 때 최소 이동 횟수

반례좀 알려주세요 ㅠㅠㅠㅠㅠ

#include<iostream>
#include<algorithm>
#include<cmath>
#define INF 2000000000
using namespace std;
int dp[21][21][21];
int arr[21];
int main()
{
	int n;
	cin >> n;
	int a, b;
	cin >> a >> b;
	int len;
	cin >> len;
	for (int i = 1; i <= len; i++)
		cin >> arr[i];
	for (int i = 0; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
				dp[i][j][k] = INF;
	if (a < b) dp[0][a][b] = 0;
	else dp[0][b][a] = 0;
	for (int i = 1; i <= len; i++) // 열려있을 벽장의 번호
	{
		for (int j = 1; j <= n; j++) 
		{
			if (j < arr[i])
			{
				for(int k=1;k<n;k++)
					for (int l = k + 1; l <= n; l++)
					{
						dp[i][j][arr[i]] = min(dp[i][j][arr[i]], dp[i - 1][k][l] + abs(j - k) + abs(arr[i] - l));
					}
			}
			else if (j > arr[i])
			{
				for (int k = 1; k < n; k++)
					for (int l = k + 1; l <= n; l++)
					{
						dp[i][arr[i]][j] = min(dp[i][arr[i]][j], dp[i - 1][k][l] + abs(j - l) + abs(arr[i] - k));
					}
			}
		}
	}
	int MIN = INF;
	for (int i = 1; i <= n; i++)
	{
		if (i < arr[len])
			MIN = min(MIN, dp[len][i][arr[len]]);
		else if(i>arr[len])
			MIN = min(MIN, dp[len][arr[len]][i]);
	}
	cout << MIN;
}

oh20020409 2년 전 0

자답합니다.

dp 배열을 초기화 할 때 아래와 같이 하였는데

for (int i = 0; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
dp[i][j][k] = INF;

첫 번째 반복 변수인 i에서 오류가 납니다.

i는 벽장문의 총 개수가 아닌 옮길 벽장문의 수이기 때문입니다.

예를들어 옮길 벽장문의 총 개수가 n보다 크다면 오류가 납니다.

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

문제

문제

출처

ICPC

반례 알려주세요!

oh20020409 2년 전 0

oh20020409 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말