글 읽기 - 1006번 초라기 문제 반례좀 같이 찾아주시면 감사하겠습니다.

chlee2734 6년 전 0

안녕하세요.

1006번 문제 반례를 찾지 못해 고전하고 있습니다 .제풀 시 50%에서 틀림으로 판정되네요.

게시판에 검색하여 skynet님이 올려주신 테스트 케이스 n이 1일 때, 2일 때, 3일 때 모두다 정확하게 나옵니다.

혹 제가 실수한 부분을 지적해 주실 수 있는 지요?

감사합니다.

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

using namespace std;


int a[2][10000];
bool v[2][10000];

int dy[] = { 1,-1,0,0 };
int dx[] = { 0, 0,1,-1 };

int n;
int w;
int cnt = 0;

void solution(int y,int x);

int main()
{
	int t;

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n >> w;

		cnt = 0;

		memset(v, false, sizeof(v));

		for (int j = 0; j < 2; j++)
		{
			for (int k = 0; k < n; k++)
			{
				cin>>a[j][k];
			}
		}
		for (int j = 0; j < 2; j++)
		{
			for (int k = 0; k < n; k++)
				solution(j, k);
		}
		for (int j = 0; j < 2; j++)
		{
			for (int k = 0; k < n; k++)
			{
				if (v[j][k] == false)
					cnt++;
			}
		}
		cout << cnt << endl;
	}



	return 0;
}
void solution(int y, int x)
{
	int max_v=a[y][x];
	int max_Y=-1,max_X=-1;
	
	if (v[y][x])
	{
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int nx = x+dx[i];
		int ny = y+dy[i];
		if (n != 1)
		{
			if (nx == -1)
				nx = n - 1;
			else if (nx == n)
				nx = 0;
		}
		if (ny < 0 || ny>1 || nx<0 || nx>n-1)
			continue;
		if (v[ny][nx])
			continue;
		if ( max_v<(a[y][x] + a[ny][nx])  && (a[y][x] + a[ny][nx]) <= w)
		{
			
			max_v = a[y][x] + a[ny][nx];
			max_Y = ny;
			max_X = nx;
		}
	}
	if (max_Y != -1 && max_X != -1) {
		v[max_Y][max_X] = true;
		v[y][x] = true;
		cnt++;
	}
	
	return;
}

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

문제

문제

출처

ICPC

1006번 초라기 문제 반례좀 같이 찾아주시면 감사하겠습니다.

chlee2734 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말