[BOJ 28356] 부정행위 멈춰!

https://www.acmicpc.net/problem/28356

28356번: 부정행위 멈춰!

 

- 문제 요약

 

김채완 교수는 “프로그래밍과 봉사” 과목의 기말고사를 준비하고 있다.

고사실은 가로 M칸, 세로 N칸인 직사각형 형태이며, 모든 칸마다 정확히 한 명의 학생이 앉게 된다.

김채완 교수는 학생들의 부정행위를 막기 위해 모든 학생이 인접한 칸의 학생과 다른 시험지를 받을 수 있도록 여러 종류의 시험지를 준비하려 한다.

이때 인접한 학생은 가로, 세로, 또는 대각선으로 붙어 있는 칸에 있는 학생을 의미한다.

김채완 교수는 많은 종류의 시험지를 준비할 시간이 없었기 때문에 시험지의 종류를 최소화하고자 한다.

가능한 한 적은 종류의 시험지를 사용하여 조건을 만족하도록 시험지를 배부하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

퍼즐 맞춘다는 생각으로 (i, j) 인덱스의 주변에 가능한 숫자들을 작은 순서로 넣어주면, 홀수 번째 줄에는 121212.... 짝수 번째 줄에는 343434... 의 형식으로 반복된다는 것을 알 수 있습니다.

N이나 M이 1인 경우에만 예외처리를 잘 해주면 단순 구현으로 풀 수 있는 문제입니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

int n,m,arr[2][4]={{1,2,1,2},{3,4,3,4}};

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    cin>>n>>m;
    if(n==1&&m==1){
		cout<<1<<'\n'<<1<<'\n';
		return 0;
	}
    if(n==1||m==1){
        cout<<2<<'\n';
        for(int i=0;i<n*m;i++){
        	if(i%2==0){
			    cout<<1;
			}
			else{
			    cout<<2;
			}
			
			if(m==1){
			    cout<<'\n';
			}
			else{
			    cout<<' ';
			}
		}
        return 0;
    }
    cout<<4<<'\n';
    for(int i=0;i<n;i++){
    	for(int j=0;j<m;j++){
    		cout << arr[i%2][j%4];
    		if(j+1==m){
			    cout<<'\n';
			}
			else{
			    cout<<' ';
			}
		}
	}
}

코드 제출 결과