[코드트리] 윷놀이 사기단

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/woodstick-fraud/description?page=2&pageSize=20

💻 문제 풀이 : C++

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

// Input 배열
int order[10];
// 0~3번 말 선택 배열
int selected[10];

// 길의 번호
int load[4];
// 지름길로 갔는지 확인
int flag[4];
int MAP[4][60];
// 길의 Idx
int PosIdx[4];
// 길의 실제 값
int PosReal[4];

int answer;

// 마지막 병합구간에서 겹칠 경우
int lastCrux(int aL, int aP, int bL, int bP)
{
	// 지름길 아닐때...ㅜ
	if (aL == 0)
	{
		if (bL == 1 && aP == 20 && bP == 12) return 0;
		if (bL == 2 && aP == 20 && bP == 16) return 0;
		if (bL == 3 && aP == 20 && bP == 22) return 0;
	}
	// 첫번째 지름길로
	if (aL == 1)
	{
		if (bL == 0 && (aP == 12) && (bP == 20)) return 0;
		if (bL == 2 && (aP >= 9))
		{
			if (bP == aP + 4) return 0;
		}
		else if (bL == 3 && (aP >= 9))
		{
			if (bP == aP + 10) return 0;
		}
	}
	// 두번째 지름길로
	else if (aL == 2)
	{
		if (bL == 0 && aP == 16 && bP == 20) return 0;
		if (bL == 1 && (aP >= 13))
		{
			if (aP == bP + 4) return 0;
		}
		else if (bL == 3 && aP >= 13)
		{
			if (aP == bP - 6) return 0;
		}
	}
	// 세번째 지름길로
	else if (aL == 3)
	{
		if (bL == 0 && aP == 22 && bP == 20) return 0;
		if (bL == 1 && aP >= 19)
		{
			if (aP == bP + 10) return 0;
		}
		else if (bL == 2 && aP >= 19)
		{
			if (bP == aP - 6) return 0;
		}
	}
	return 1;
}

int isOkay()
{
	for (int i = 0; i < 4; i++)
	{
		// 시작할때는 겹쳐서 출발
		if (PosReal[i] == 0) continue;
		for (int j = i + 1; j < 4; j++)
		{
			// 시작할때는 겹쳐서 출발
			if (PosReal[j] == 0) continue;
			// 지름길, 길 Idx 각각 비교
			if (load[i] == load[j] &&
				PosIdx[i] == PosIdx[j]) return 0;
			// 마지막 병합구간 겹치는지 확인
			if (!lastCrux(load[i], PosIdx[i], load[j], PosIdx[j])) return 0;
		}
	}
	return 1;
}

int getScore()
{
	int score = 0;
	for (int q = 0; q < 10; q++)
	{
		PosIdx[selected[q]] += order[q];
		if (PosIdx[selected[q]] == 5)
		{
			flag[selected[q]] = 1;
			load[selected[q]] = 1;
		}
		if (flag[selected[q]] == 0 && PosIdx[selected[q]] == 10)
		{
			flag[selected[q]] = 1;
			load[selected[q]] = 2;
		}
		if (flag[selected[q]] == 0 && PosIdx[selected[q]] == 15)
		{
			flag[selected[q]] = 1;
			load[selected[q]] = 3;
		}
		PosReal[selected[q]] = MAP[load[selected[q]]][PosIdx[selected[q]]];
		if (!isOkay()) return 0;
		// 도착 처리 
		score += PosReal[selected[q]];
	}
	return score;
}


void dfs(int depth)
{
	if (depth == 10)
	{
		memset(PosReal, 0, sizeof(PosReal));
		memset(PosIdx, 0, sizeof(PosIdx));
		memset(flag, 0, sizeof(flag));
		memset(load, 0, sizeof(load));
        
		answer = max(answer, getScore());
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		selected[depth] = i;
		dfs(depth + 1);
		selected[depth] = 0;
	}
}

void CLEAR()
{

}

void INPUT()
{
	for (int i = 0; i < 10; i++)
	{
		cin >> order[i];
	}
	for (int j = 0; j <= 3; j++)
	{
		for (int i = 1; i <= 20; i++)
		{
			MAP[j][i] = 2 * i;
		}
		if (j == 1)
		{
			MAP[j][6] = 13;
			MAP[j][7] = 16;
			MAP[j][8] = 19;
			MAP[j][9] = 25;
			MAP[j][10] = 30;
			MAP[j][11] = 35;
			MAP[j][12] = 40;
			for (int k = 13; k <= 20; k++)
				MAP[j][k] = 0;
		}
		else if (j == 2)
		{
			MAP[j][11] = 22;
			MAP[j][12] = 24;
			MAP[j][13] = 25;
			MAP[j][14] = 30;
			MAP[j][15] = 35;
			MAP[j][16] = 40;
			for (int k = 17; k <= 20; k++)
				MAP[j][k] = 0;
		}
		else if (j == 3)
		{
			MAP[j][16] = 28;
			MAP[j][17] = 27;
			MAP[j][18] = 26;
			MAP[j][19] = 25;
			MAP[j][20] = 30;
			MAP[j][21] = 35;
			MAP[j][22] = 40;
		}
	}
}

void SOLVE()
{
	dfs(0);
	cout << answer << endl;
}

int main()
{
	CLEAR();
	INPUT();
	SOLVE();

	return 0;
}

📌 memo 😊
4 4 4 * ... 10번
=> 4^10 개