[알고리즘] 빙고 [KOI 2006_2]
코덕질/해탈내역들 2008/12/18 18:53
문제는 중등부 정보올림피아드 2006년도 본선 2번째 문제입니다.
소스는 bingo.h와 main.cpp로 이루어져 있습니다.
문제 보기...
빙고
빙고 게임은 다음과 같은 방식으로 이루어진다.
먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다.
다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5, 10, 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다.
차례로 수를 지워가다가 같은 가로줄, 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다.
이러한 선이 세 개 이상 그어지는 순간 ‘빙고’라고 외치는데 가장 먼저 ‘빙고’라고 외친 사람이 게임의 승자가 된다.
철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때, 사회자가 몇 번째 수를 부른 후 철수가 ‘빙고’를 외치게 되는지를 출력하는 프로그램을 작성하시오.
실행파일의 이름은 BINGO.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.
입력 형식
입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다.
출력 형식
출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에 사회자가 몇 번째 수를 부른 후 철수가 ‘빙고’를 외치게 되는지 출력한다.
입력과 출력의 예
빙고 게임은 다음과 같은 방식으로 이루어진다.
먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다.
다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5, 10, 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다.
실행파일의 이름은 BINGO.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.
입력 형식
입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다.
출력 형식
출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에 사회자가 몇 번째 수를 부른 후 철수가 ‘빙고’를 외치게 되는지 출력한다.
입력과 출력의 예
소스는 bingo.h와 main.cpp로 이루어져 있습니다.
main.cpp
#include <stdio. h>
#include "bingo.h"
int main()
{
bool bingo_selected[25]; //빙고판에서의 체크 여부
int bingo_num[25]; //빙고판에 쓴 숫자의 배열
int bingo_order[25]; //사회자가 차례대로 부를 숫자의 배열
FILE *fp;
fp = fopen("input.txt", "r");
if (fp==NULL) return -1;
// 빙고판에 쓴 숫자의 배열을 읽어들인다
for (int i=0;i<25;i++)
fscanf(fp, "%d", &bingo_num[i]);
// 사회자가 차례대로 부를 숫자의 배열을 읽어들인다
for (int i=0;i<25;i++)
fscanf(fp, "%d", &bingo_order[i]);
// 파일 읽기가 끝났으면 닫는다
fclose(fp);
// bingo_selected를 false로 초기화한다
for (i=0;i<25;i++)
bingo_selected[i] = false;
/////////////////////////////////
// 본격 알고리즘 루틴 ////////////
/////////////////////////////////
int sum=0, index=0; // 빙고의 수를 저장할 배열
for (int i=0;i<25;i++)
{
// 빙고에 체크되면서 그자리에서 생성되는 빙고 수를 더한다
sum += CheckBingo(bingo_selected, bingo_num, bingo_order[i]);
// 만약 sum(빙고 수)가 3 이상이면 for구문에서 빠져나간다
if (sum>=3)
{
index=i;
break;
}
}
// 결과값(최초로 빙고 수가 3개가 되었을때의 index값)을 output.txt로 출력한다
fp = fopen("output.txt", "w+");
fprintf(fp, "%d", index+1);
fclose(fp);
}
bingo.h
int CheckBingo(bool *bingo_selected, int *bingo_num, const int i_check)
{
int check_num; // 체크될 빙고판의 위치
for (check_num=0;check_num<25;check_num++)
{
// 만약 이미 검사하려고 하는 칸의 빙고판이 체크되었다면 생략
if (!bingo_selected[check_num])
{
// 사회자가 불러주신 숫자와 검사하려는 빙고판에 쓴 숫자가 일치하면 빙고판(bingo_selected)를 체크(true)
if (bingo_num[check_num]==i_check)
{
bingo_selected[check_num]=true;
int cnt_bingo=0; // 사회자가 불러준 숫자의 빙고의 수를 저장할 변수
int pos_x, pos_y; // 빙고를 체크한 곳의 x,y좌표를 저장할 변수
// x좌표 구하기
pos_x = check_num%5;
// y좌표 구하기
pos_y = check_num/5;
// 가로 빙고 체크
if (bingo_selected[pos_y*5+0] && bingo_selected[pos_y*5+1] && bingo_selected[pos_y*5+2] && bingo_selected[pos_y*5+3] && bingo_selected[pos_y*5+4]) cnt_bingo++;
// 세로 빙고 체크
if (bingo_selected[pos_x+0] && bingo_selected[pos_x+5] && bingo_selected[pos_x+10] && bingo_selected[pos_x+15] && bingo_selected[pos_x+20]) cnt_bingo++;
// 가로와 세로가 같을 때에는 음의 방향 대각선 빙고 체크
if (pos_x==pos_y)
{ if (bingo_selected[0] && bingo_selected[6] && bingo_selected[12] && bingo_selected[18] && bingo_selected[24]) cnt_bingo++; }
// 가로와 (4-세로)가 같을 때에는 양의 방향 대각선 빙고 체크
if (pos_x==(4-pos_y))
{ if (bingo_selected[4] && bingo_selected[8] && bingo_selected[12] && bingo_selected[16] && bingo_selected[20]) cnt_bingo++; }
// cnt_bingo값을 리턴한다
return cnt_bingo;
}
}
}
// (아마 그럴 리는 없겠지만) 이 루틴에 해당사항이 없는 경우 return 0을 한다
return 0;
}
[KOI] 2006_2.rar
댓글을 달아 주세요
비밀댓글입니다
지금은 시간이 없어서 주말에 마저 할 예정.. 그리고 이런 글은 방명록에 ^^
엑박이 나오는 저에겐...
(그나저나 오랜만에보는 엑박..+ _+)
원본 사이트 kado에서 링크를 막은 듯 싶네요 -_-. 직접 걸어야 하나...