글 읽기 - 주사위 윷놀이 74%에서 틀립니다. 도와주세요~

hw2621 4년 전 1

중복순열로 가능한 모든 경우의 수를 탐색했습니다.

예제는 다 맞고 제출 시 74%에서 틀렸다고 나오네요.

말의 이동은

말의 위치와 말이 타고있는 화살표 색깔을 저장해 해당 정보에 맞게 이동하도록 했습니다.

코드를 조금씩 수정해서 말을 움직인 횟수를 구해 10번일 때, 0번이 아닐 때 점수를 갱신하도록 해도 다 틀렸다고 나오네요. 어디가 문제일까요?

#include <iostream>
using namespace std;

int mal_col[4] = { 0, };
int mal_pos[4] = { 0, };
int existed[42][2] = { 0, };
int move_mal[10];
int is_dochak[4] = { 0, };
int dice[10];
int max_score = 0;

void init()
{
	for (int i = 0; i < 4; i++)
	{
		mal_col[i] = 0; mal_pos[i] = 0; is_dochak[i] = 0;
	}
	for (int i = 0; i < 42; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			existed[i][j] = 0;
		}
	}
}

void move(int i, int& score, bool& moved)
{
	int col, pos, ncol, npos;
	col = mal_col[move_mal[i]]; pos = mal_pos[move_mal[i]];
	ncol = col; npos = pos;
	//이미 도착한 말을 움직이려 할 경우 바로 함수 종료
	if (pos > 40) { moved = false; return; }
	if (col == 1)
	{
		if (pos == 10 || pos == 13 || pos == 16 || pos == 19)
		{
			npos = pos + 3 * dice[i];
			if (npos > 19)
			{
				int cnt = (npos - 22) / 3;
				npos = 25 + cnt * 5;
				ncol = 0;
			}
			
		}
		else if (pos == 20 || pos == 22 || pos == 24)
		{
			npos = pos + 2 * dice[i];
			if (npos > 24)
			{
				int cnt = (npos - 26) / 2;
				npos = 25 + cnt * 5;
				ncol = 0;
			}
			
		}
		else if (pos == 30 || pos == 28 || pos == 27 || pos == 26)
		{
			if (pos == 30)
				npos = pos - 2 - dice[i] + 1;
			else
				npos = pos - dice[i];
			if (npos < 25)
			{
				int cnt = (25 - npos);
				npos = 25 + cnt * 5;
				ncol = 0;
			}
			
		}
	}
	else
	{
		if (pos == 25 || pos == 30 || pos == 35 || pos == 40)
		{
			npos = pos + 5 * dice[i];
			
		}
		else
		{
			npos = pos + 2 * dice[i];
			if (npos == 10 || npos == 20 || npos == 30) ncol = 1;
		}
	}
	if (npos > 40)
	{ 
		npos = 41; 
		mal_pos[move_mal[i]] = 41;  is_dochak[move_mal[i]] = 1;
		existed[pos][col] = 0; existed[npos][ncol] = 1;
		return;
	}
	if (existed[npos][ncol] == 1) 
	{ 
		//cout << npos << "," << ncol << " 위치에 딴 말이 있습니다\n";
		moved = false;
		return; 
	}
	else
	{
		existed[pos][col] = 0; existed[npos][ncol] = 1;
		//cout << pos << "," << col << " e[][] = 0\n";
		//cout << npos << "," << ncol << " e[][] = 1\n";
		mal_pos[move_mal[i]] = npos; mal_col[move_mal[i]] = ncol;
		score += npos;
		return;
	}
}

void solve(int cnt)
{
	if (cnt == 10)
	{
		for (int i = 0; i < 4; i++)
		{
			mal_col[i] = 0; mal_pos[i] = 0;
			is_dochak[i] = 0;
		}
		for (int i = 0; i < 42; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				existed[i][j] = 0;
			}
		}
		int score = 0;
		for (int i = 0; i < 10; i++)
		{	
			bool moved = true;
			move(i, score, moved);
			if (!moved) return;
		}
		
		if (score > max_score)
		{
			max_score = score;
			/*for (int i = 0; i < 10; i++)
			{
				cout << move_mal[i];
			}
			cout << "\n";
			cout << score << "\n";*/
		}
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		move_mal[cnt] = i;
		solve(cnt + 1);
	}
}

int main()
{
	
	for (int i = 0; i < 10; i++)
	{
		cin >> dice[i];
	}
	init();
	solve(0);
	cout << max_score << "\n";
	/*
	init(); int score = 0;
	for (int i = 0; i < 10; i++)
	{
		move(i, score);
		cout << move_mal[i] << " " << mal_pos[move_mal[i]] << " " << score << "\n";
	}
	*/
	return 0;
}

danimartinwife 4년 전 1

전체적인 로직이 저랑 비슷한거 같은데, 저도 90% 정답률 나와서 테스트케이스 제가 틀린거 첨부합니다.

(우선 반례는 인터넷 뒤져도 다 맞아서, 제가 만들어서 정답소스 돌려서 제 아웃풋이랑 차이 확인했습니다)

5 5 5 5 5 1 1 1 1 1
ans 167

5 5 5 5 5 2 2 2 2
ans 160

5 5 5 5 5 2 2 1 3
ans 161

hw2621 4년 전 0

답변 감사합니다~ 2번째와 3번째는 숫자가 9개라 테스트해보지 못했고, 1번째 경우는 맞게 나오네요. 저도 테스트케이스를 직접 만들어서 정답소스랑 비교하면서 해봐야겠네요. 좋은 하루 되세요~

flytmdgh 4년 전 0

2 번째 3번째 꺼는 2랑 3각각 추가하시면 될듯해요

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

문제

문제

출처

ICPC

주사위 윷놀이 74%에서 틀립니다. 도와주세요~

hw2621 4년 전 1

danimartinwife 4년 전 1

hw2621 4년 전 0

flytmdgh 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말