Computer Science/Algorithm Problem

백준] 2578 - 빙고(한국정보올림피아드 2006;KOI 2006 지역본선)

TwinParadox 2018. 8. 16. 07:17
728x90

시간 제한 : 1초

메모리 제한 : 128MB




입력

첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다.




출력

첫째 줄에 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지 출력한다.




소스코드

#include <iostream>
using namespace std;
int board[5][5];
bool isCheck[5][5];
int calls[25];
void check(int n)
 {
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			if (board[i][j] == n)
				isCheck[i][j] = true;
}
int bingo()
{
	int cnt, lines = 0;
	for (int i = 0; i < 5; i++)
	{
		for (cnt = 0; cnt < 5; cnt++)
			if (isCheck[i][cnt] == false)
				break;
		if (cnt == 5)
			lines++;
		for (cnt = 0; cnt < 5; cnt++)
			if (isCheck[cnt][i] == false)
				break;
		if (cnt == 5)
			lines++;
	}

	for (cnt = 0; cnt < 5; cnt++)
		if (isCheck[cnt][cnt] == false)
			break;
	if (cnt == 5)
		lines++;

	for (cnt = 0; cnt < 5; cnt++)
		if (isCheck[4 - cnt][cnt] == false)
			break;
	if (cnt == 5)
 		lines++;

	return lines;
}
int main(void)
{
	int cnt;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			cin >> board[i][j];
			isCheck[i][j] = false;
		}
	}

	for (int i = 0; i < 25; i++)
		cin >> calls[i];

	for (cnt = 0; cnt < 25; cnt++)
	{
		check(calls[cnt]);
		if (bingo() >= 3)
		{
			cout << cnt + 1;
			break;
		}
	}
}




Tip

3줄 이상 빙고를 완성하면 몇 번째 불렀는지 출력하는 문제다.

가로, 세로, 대각선을 체크해주면 되는 문제이며, 최소 12개의 숫자를 불러야 3줄 빙고가 가능하다는 점을 이용하자. 코드에서는 12번 이상부터 체크하진 않았다.



728x90