글 읽기 - 왜 틀렸을까요?? 다른 올려주셨던 테케도 다 맞는데 원인좀 찾아주세요

kdy3699 6년 전 0

풀이 방식은 한점에서 두블럭을 커버 할 수 있는 경우를 숫자로 저장해 놓고 개수가 가장 적은것 부터 한묶음씩 소거해 가는 방식으로 했어요 소스가 좀 더러워서 ㅎㅎ 반례가 있다면 부탁드립니다.

#include<iostream>
using namespace std;

int main()
{
	int tcase = 0;
	cin >> tcase;
	for (int q = 0; q < tcase; q++)
	{
		int n, w, count = 0, max = 0;
		cin >> n >> w;
		int num[10002][4];
		int a[10002][4] = { 0, };
		for (int i = 0; i < 4; i++)
		{
			for (int j = 0; j < 10002; j++)
			{
				num[j][i] = 10001;
			}
		}
		for (int i = 1; i <= 2; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				cin >> num[j][i];
			}
		}
		num[0][1] = num[n][1];
		num[0][2] = num[n][2];
		num[n + 1][1] = num[1][1];
		num[n + 1][2] = num[1][2];
		for (int i = 1; i <= 2; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (num[j][i] + num[j + 1][i] <= w)
					a[j][i]++;
				if (num[j][i] + num[j - 1][i] <= w)
					a[j][i]++;
				if (num[j][i] + num[j][i + 1] <= w)
					a[j][i]++;
				if (num[j][i] + num[j][i - 1] <= w)
					a[j][i]++;
				if (a[j][i] > max)
					max = a[j][i];

			}
		}
		a[0][1] = a[n][1];
		a[0][2] = a[n][2];
		a[n + 1][1] = a[1][1];
		a[n + 1][2] = a[1][2];

		for (int x = 0; x <= max * 2; x++)
		{
			for (int i = 1; i <= 2; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					if (a[j][i] == x)
					{
						if (x == 0)
							count++;
						else
						{
							if (num[j][i] + num[j][i + 1] <= w&&a[j][i + 1] != 0)
							{
								count++;
								a[j][i] = 0;
								a[j][i + 1] = 0;
								if (j == n)
								{
									a[0][i] = 0;
									a[0][i + 1] = 0;
								}
								if (j == 1)
								{
									a[n + 1][i] = 0;
									a[n + 1][i + 1] = 0;
								}
							}
							else if (num[j][i] + num[j][i - 1] <= w&&a[j][i - 1] != 0)
							{
								count++;
								a[j][i] = 0;
								a[j][i - 1] = 0;
								if (j == n)
								{
									a[0][i] = 0;
									a[0][i - 1] = 0;
								}
								if (j == 1)
								{
									a[n + 1][i] = 0;
									a[n + 1][i - 1] = 0;
								}
							}
							else if (num[j][i] + num[j + 1][i] <= w&&a[j + 1][i] != 0)
							{
								count++;
								a[j][i] = 0;
								a[j + 1][i] = 0;
								if (j == n)
								{
									a[1][i] = 0;
								}
							}
							else if (num[j][i] + num[j - 1][i] <= w&&a[j - 1][i] != 0)
							{
								count++;
								a[j][i] = 0;
								a[j - 1][i] = 0;
								if (j == 1)
								{
									a[n][i] = 0;
								}
							}
							
						}
						a[0][1] = a[n][1];
						a[0][2] = a[n][2];
						a[n + 1][1] = a[1][1];
						a[n + 1][2] = a[1][2];
					}
				}
			}
		}
		for (int i = 1; i <= 2; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (a[j][i] != 0)
					count++;
			}
		}
		cout << count << endl;
	}
}

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

문제

문제

출처

ICPC

왜 틀렸을까요?? 다른 올려주셨던 테케도 다 맞는데 원인좀 찾아주세요

kdy3699 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말