https://www.acmicpc.net/problem/2447
문제
입력
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
예제 입력
풀이과정
문제의 패턴을 찾는데 꽤나 오랜 시간이 걸린 것 같다.
N이 3일 때는 3 3크기의 정사각형이 출력되어야한다. 이때, 가운데는 N/3 N/3 크기만큼 공백이 존재해야한다.
따라서 N이 3일 때의 출력은 다음과 같다.
***
* *
***N이 3보다 클 경우, 예를 들어 9일 때 패턴은 가운데 N/3 * N/3 크기만큼 공백이 채워지고 나머지 부분은 N/3의 패턴으로 둘러싼 형태라고한다. 출력은 다음과 같을 것이다.
*********
* ** ** *
*********
*** ***
* * * *
*** ***
*********
* ** ** *
*********N이 27일 경우에는 위의 예제 출력과 같다.
현재 공백이 찍히는 패턴은 N과 밀접한 연관이 있다는 것을 알 수 있다. 별이 찍히는 위치를 이차원 배열의 인덱스라고 생각해보자.
N이 3일 때 공백이 찍히는 인덱스는 1,1이다.
그리고 조금 더 넓게 보기 위해 N이 9라고 가정해보자. (N이 9일 때 별이 출력되는 것은 위에 나와있다.)
그렇다면 공백이 찍히는 인덱스는
1,1 4,1 7,1
1,4 (3~5,3) 7,4
(3~5,4)
(3~5,5)
1,7 4,7 7,7
이다.
여기서 중요한 점이 있다. 가운데 공백이 한번 찍히는 처음 위치는 (1,1)이다. (N==3일 때의 패턴)
가운데 공백이 한 번 찍히는 다른 정사각형의 인덱스를 3으로 나눈 나머지를 구해보자.
(4,1) (7,1) (7,4) 등등 모두 3으로 나눈 나머지는 1,1이다. 즉, 정사각형의 위치가 어디에 떨어져있든 일정한 간격을 두고 똑같은 정사각형을 이룬다는 뜻이다.
이번엔 하나의 공백이 아닌 여러개의 공백으로 채워져있는 N이 9일 때의 패턴을 보자.
3 3 크기의 공백이 채워져있다. N이 27이라면 아래 이미지와 같이 가운데에 3 3 크기의 공백이 채워져있는 N이 9인 패턴의 정사각형이 많이 늘어날 것이다.
이의 해결법 또한 위에서 알아보았던, 정사각형의 위치가 어디에 있든 동일한 패턴의 정사각형들은 결국 일정한 위치만큼 떨어져있다라는 사실을 이용하면 된다.
첫 번째 줄과 두 번째 줄에서 3 * 3 크기의 공백을 갖는 정사각형의 위치를 보면 다음과 같다.
(3~5,3) (10~12,3) (19~21,3)
(3~5,4) (10~12,4) (19~21,4)
(3~5,5) (10~12,5) (19~21,5)
(3~5,12) (10~12,12) (19~21,12)
(3~5,13) (10~12,13) (19~21,13)
(3~5,14) (10~12,14) (19~21,14)
다시 9로 나눈 나머지를 구해보면 x축과 y의 범위가 다음과 똑같다는 것을 알 수 있다.
(3~5,3)
(3~5,4)
(3~5,5) 모든 정사각형들은 이러한 위치 패턴을 띄므로 이중 반복문을 사용해 정답을 구할 수 있다.
다음은 java로 구현한 풀이 코드이다.
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for( int i = 0; i < N; i++ ){
for( int j = 0; j < N; j++ ){
int tempRow = i;
int tempHigh = j;
int tempN = N;
// 3으로 나눈 나머지가 row, high 모두 1이라면 공백
if( tempRow%3 == 1 && tempHigh%3 == 1 ) {
sb.append(' ');
}else{
while( true ){
// N으로 나눈 나머지는 N/3 패턴을 가진 정사각형
tempRow %= tempN; tempHigh %= tempN;
// N을 3으로 나눠가며
// tempRow와 tempHigh가 공백이 위치한 영역에
// 있는지 확인
tempN /= 3;
if( 3 > tempRow || 3 > tempHigh) {
sb.append('*');
break;
}
// 만약 공백이 위치해야하는 곳이라면 공백 출력
if( (tempN*2-1 >= tempRow && tempRow >= tempN) && (tempN*2-1 >= tempHigh && tempHigh >= tempN )) {
sb.append(' ');
break;
}
}
}
}
sb.append("\n");
}
System.out.println(sb);
}
}