글 읽기 - 반례나 잘못된 알고리즘을 찾아주시면 감사하겠습니다.

smugc201811147 5년 전 0

안녕하세요. dp를 막 공부하고 있는 학생입니다.

다름이 아니라, 아래 코드의 잘못 된 부분이나 반례를 찾고 싶어 질문 게시판에 글을 작성하게 되었습니다.

제가 생각 할 수 있는 범위 내에서의 출력값은 제대로 나오는 듯 하나, 백준 제출 시 [틀렸습니다]를 받고 있어 어느 부분이 문제인지 알고 싶습니다.

도움 주신다면 감사하겠습니다 ;ㅁ; .

#include <iostream>
#include <algorithm>
using namespace std;

#define even(X) (!(X%2))

//전역 변수
int pattern_DDR[100050] = { 0, };
int pattern_DDRCount = 0;

int dp[100050][10][10] = { { {0,} } };

void getValue()
{
	while (true)
	{
		cin >> pattern_DDR[pattern_DDRCount];

		if (pattern_DDR[pattern_DDRCount] == 0)
		{
			break;
		}
		pattern_DDRCount++;
	}
}

int moveDDRplay(int node, int left, int right)
{	
	if (node >= pattern_DDRCount)
	{
		return 0;
	}

	int &ret = dp[node][left][right];
	if (ret != 0)
	{
		return ret;
	}
	ret = 20000000;

	// 문제처럼 각 방향을 1, 2, 3, 4로 지정했을 때,
	// 현재 밟아야 하는 위치와 현재 나의 발 위치가 같으면 +1.
	// "현재 밟아야 하는 위치 - 현재 나의 발 위치"가 짝수면 +4 (서로 반대방향.)
	// "현재 밟아야 하는 위치 - 현재 나의 발 위치"가 홀수면 +3 (서로 인접한 방향.)
	// 나의 발 위치가 0이면, 다음에 누를 때는 무조건 +2.

	//왼발 움직임.
	if (pattern_DDR[node] != right)
	{
		if (left == 0)
		{
			ret = min(ret, 2 + moveDDRplay(node + 1, pattern_DDR[node], right));
		}
		else if (pattern_DDR[node] == left)
		{
			ret = min(ret, 1 + moveDDRplay(node + 1, pattern_DDR[node], right));
		}
		else if (even(pattern_DDR[node] - left))
		{
			ret = min(ret, 4 + moveDDRplay(node + 1, pattern_DDR[node], right));
		}
		else
		{
			ret = min(ret, 3 + moveDDRplay(node + 1, pattern_DDR[node], right));
		}
	}
	
	//오른발 움직임.
	if (pattern_DDR[node] != left)
	{
		if (right == 0)
		{
			ret = min(ret, 2 + moveDDRplay(node + 1, left, pattern_DDR[node]));
		}
		else if (pattern_DDR[node] == right)
		{
			ret = min(ret, 1 + moveDDRplay(node + 1, left, pattern_DDR[node]));
		}
		else if (even(pattern_DDR[node] - right))
		{
			ret = min(ret, 4 + moveDDRplay(node + 1, left, pattern_DDR[node]));
		}
		else
		{
			ret = min(ret, 3 + moveDDRplay(node + 1, left, pattern_DDR[node]));
		}
	}
	// cout << "dp[" << node << "][" << left << "][" << right << "]: " << dp[node][left][right] << endl;

	return ret;
}

void printResult(int result)
{
	cout << result;
}

int main()
{
	getValue();
	int result = moveDDRplay(0, 0, 0);
	printResult(result);
}

smugc201811147 5년 전 0

슬랙에서 어떤 능력자(!)분이 해결해 주셨으나 혹시나 저와 비슷한 실수를 하실 분이 싶어 문제점을 남겨둡니다.

#define even(X) (!(X%2)) , 즉 매크로 함수가 문제였는데요.

짝수를 판별하려는 용도로 만들었기에, even(pattern_DDR[node] - right) 이런 식으로 코드에 작성하였으나

even 매크로 함수의 안이 치환되면

(!(pattern_DDR[node]-right%2)) 가 되고, -보다 %가 연산자 우선순위가 높기 때문에 연산에서 오류가 나는 것이였습니다.

이전에 예제라던지 올바른 값이 나온건 순전이 운이였던 듯.. 싶습니다만,

혹시나 저처럼 매크로 함수를 썼다가 고생하시는 분이 생길까 싶어 댓글로 남겨두겠습니다.

매크로 함수를 사용하지 않거나,

#define even(X) (!((X)%2)) 로 바꾸니 해결되었습니다.

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

문제

문제

출처

ICPC

반례나 잘못된 알고리즘을 찾아주시면 감사하겠습니다.

smugc201811147 5년 전 0

smugc201811147 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말