글 읽기 - 맞았지만 궁금한 점

minjun13795 4년 전 0

'틀렸습니다'가 나와서 46번째 줄 N-1을 N-2로 고쳐봤더니 맞았습니다.

제가 고쳐준 이유는 N이 15가 들어왔을 때 배열 범위가 벗어나는 '런타임 에러' 때문에 고쳤는데 '틀렸습니다'가 해결이 됐네요...

N-1로 했을 때 틀릴 수 있는 반례는 무엇이죠?

어차피 N과 M의 범위에 벗어나는 데이터는 버려도 된다고 생각하는데 말입니다..

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <functional>
typedef long long ll;
typedef std::pair<int, int> pi;
typedef std::pair<pi, pi> pii;
using namespace std;
int N, M, D;
int map[15][15];
int copyMap[15][15];
int max(int a, int b)
{
	return a < b ? b : a;
}
int abs(int a)
{
	return a > 0 ? a : -a;
}

int calc(int r1, int c1, int r2, int c2)
{
	return abs(r1 - r2) + abs(c1 - c2);
}
bool isend()
{
	bool check = false;

	for (int j = 0; j < N; j++)
		for (int i = 0; i < M; i++)
			if (copyMap[j][i] == 1)
				check = true;

	if (!check)
		return true;

	return false;
}

void next_turn()
{
	for(int j = N - 1; j >= 0 ; j--)
		for (int i = 0; i < M; i++)
			copyMap[j+1][i] = copyMap[j][i];

	for (int i = 0; i < M; i++)
		copyMap[0][i] = 0;

	for (int j = N - 1; j >= 0; j--)
		for (int i = 0; i < M; i++)
			if (copyMap[j][i] == -1)
				copyMap[j][i] = 0;
}

int main()
{
	scanf("%d %d %d", &N, &M, &D);
	for (int j = 0; j < N; j++)
		for (int i = 0; i < M; i++)
			scanf("%d", &map[j][i]);

	int ret = 0;
	for (int i = (1 << 3) - 1; i <= (((1 << 3) - 1) << (M - 3)); i++)
	{
		memcpy(copyMap, map, sizeof(map));
		vector<int> bow;

		for (int j = 0; j < M; j++)
			if ((i & (1 << j)) != 0)
				bow.push_back(j);

		if (bow.size() != 3)
			continue;

		int temp = 0;

		while(true)
		{
			for (auto iter : bow)
			{
				pair<int, int> target = make_pair(987654321, 987654321);
				int tempD = D;
				for (int j = N - 1; j >= 0; j--)
					for (int k = 0; k < M; k++)
					{
						if (calc(k, j, iter, N) < tempD && copyMap[j][k] != 0)
						{
							tempD = calc(k, j, iter, N);
							target.first = k;
							target.second = j;
						}
						else if (calc(k, j, iter, N) == tempD && copyMap[j][k] != 0 && k < target.first)
						{
							target.first = k;
							target.second = j;
						}
					}
				if (target.first != 987654321)
				{
					if (copyMap[target.second][target.first] == 1)
						temp++;

					copyMap[target.second][target.first] = -1;
				}
			}
			next_turn();

			if (isend())
				break;
		}

		ret = max(temp, ret);
		bow.clear();
	}

	printf("%d", ret);
	return 0;
}

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

문제

문제

출처

ICPC

맞았지만 궁금한 점

minjun13795 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말