글 읽기 - 17136번 17%대에서 틀렸습니다.. 무엇을 놓치고 있는걸까요?

isyou7487 3년 전 0

우선 1의 위치는 y와 x가 아닌 1차원배열같이 생각하여 0~99까지의 정수로 저장했습니다.

1의 위치를 나타내는 list의 0번 index부터 시작해 list의 끝까지 탐색을 하며 길이가 1,2,3,4,5인 색종이를 덮어봤습니다.

covered를 이용해 전번 index에서 덮여진 1이 나왔을때는 덮지않고 다음 index로 넘어가게끔 했습니다.

chosen 배열은 말 그대로 길이 별로 색종이가 선택 된 개수이며 index가 리스트의 마지막에 도달하면 최소값을 갱신하도록 짰습니다..

게시판에 있는 테케란 테케는는 다 돌려봤는데 답이 다 제대로 나옵니다 ㅠㅠ

무엇이 문제일까요?

using System;
using System.Collections.Generic;

public class Test
{
	static int [][] board = new int[10][];
	static bool [][] covered = new bool[10][];
	static List<int> list = new List<int>();
	static int [] chosen = new int[5];
	const int INF = 987654321;
	static int MIN = INF;
	public static void Main()
	{
		string [] s;
		for(int i=0 ;i<5; i++)
		{
			chosen[i] = 0;
		}
		for(int i=0; i<10; i++)
		{
			s = Console.ReadLine().Split(' ');
			board[i] = new int[10];
			covered[i] = new bool[10];
			for(int j=0; j<10; j++)
			{
				board[i][j] = int.Parse(s[j]);
				covered[i][j] = false;
				if(board[i][j] == 1)
					list.Add(i*10 + j);
			}
		}
		findMin(0);
		if(MIN == INF)
			Console.WriteLine("-1");
		else
			Console.WriteLine(MIN);
	}
	
	public static void findMin(int index) // index는 1의 위치를 순서대로 나열했을때 위치
	{
		bool coveredOnce = false;
		if(index >= list.Count)
		{
			int sum = chosen[0] + chosen[1] + chosen[2] + chosen[3] + chosen[4];
			MIN = sum < MIN ? sum : MIN;
			return ;
		}
		if(chosen[0] >= 5 || chosen[1] >= 5 || chosen[2] >= 5 || chosen[3] >= 5 || chosen[4] >=5)
			return ;
		for(int i=1; i<=5; i++)
		{
			if(canCover(list[index] ,i))
			{
				
				Cover(list[index], i, true);
				chosen[i-1] ++;
				//Show();
				findMin(index+1);
				chosen[i-1] --;
				Cover(list[index] , i, false);
				coveredOnce = true;
			}
		}
		if(!coveredOnce)
		{
			findMin(index+1);
		}
	}
	
	public static void Cover(int index, int length, bool isCover)
	{
		int y = index/10;
		int x = index%10;
		
		for(int i=1; i<=length; i++)
		{
			for(int j=1; j<=length; j++)
			{
				covered[y+i-1][x+j-1] = isCover;
			}
		}
	}
	
	public static bool canCover(int index, int length)
	{
		bool cancover = true;
		int y = index/10;
		int x = index%10;
		if(!inRange(y+length -1, x+length -1))
			return false;
		for(int i=1; i<=length; i++)
		{
			for(int j=1; j<=length; j++)
			{
				if(board[y+i-1][x+j-1] == 0 || covered[y+i-1][x+j-1])
				{
					cancover = false;
					break;
				}
			}
		}
		return cancover;
	}
	public static bool inRange(int y, int x)
	{
		if(y<0 || y>9 || x<0 || x>9)
			return false;
		return true;
	}
}

luck 3년 전 1

if(chosen[0] >= 5 || chosen[1] >= 5 || chosen[2] >= 5 || chosen[3] >= 5 || chosen[4] >=5)

return ;

로 return을 해주면 안됩니다.

예를 들어, 1 크기 색종이는 5개로 다 붙어졌어도,

2 크기 색종이로 붙일 수 있는 경우가 있기 때문입니다.

isyou7487 3년 전 0

정말 감사합니다 !!

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

문제

문제

출처

ICPC

17136번 17%대에서 틀렸습니다.. 무엇을 놓치고 있는걸까요?

isyou7487 3년 전 0

luck 3년 전 1

isyou7487 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말