[백준]2447번 별 찍기 - 10

문제

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

 

 

 

 

풀이 

고려해야할 점

• *를 어떤 방법으로 찍을 것인가
• 결과 출력

알고리즘

• 재귀

풀이 설명

1. * 찍기

먼저 n*n 크기의 2차원 배열을 선언하고 여기에 출력 값을 저장한다. 재귀함수를 통해 *을 찍어야 하는 곳의 위치를 구한 뒤 해당 위치에 *을 할당하고 배열을 출력한다. 

 

재귀함수는 f(x,y,d)의 형식으로 호출한다. x, y는 x, y 좌표이며 d는 처음에는 입력 값의 지수(입력 = 3^m에서 m의 값)를 할당해 준 다음 재귀 호출시마다 값을 1씩 감소한다. 

x,y	x+3^m,y	x+2*3^m ,y
x, y+ 3^m		x+2*3^m ,y+ 3^m
x, y+2* 3^m	x+3^m, y+2*3^m	x+2*3^m , y+2* 3^m

함수 호출 시 d의 값이 0이 될 경우 해당 좌표애 *을 찍는다. 

 

2. 출력 

출력 때문에 시간 초과가 되었다. 2차원 배열의 최대 크기가 (3^8)^2이며 이때 실행시간이 오래 걸리는 print 함수를 사용하며 시간 초과로 실패한다.  그러므로 StringBuilder로 출력 값을 저장한 다음 마지막에 한 번에 출력하는 방식으로 바꾸었다. 

 

코드

import java.util.Scanner;
import java.util.Arrays;
import java.lang.Math;

class Main {
	public static void main(String []args) {
    	//입력 
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n = sc.nextInt();
		int m = 0, temp = n;
        
        //3^m, 지수 구하기 
		while(temp!=1) {
			temp = temp/3;
			m++;
		}
		
        //  n*n 2차원 배열의 값을 " "로 초기화 
		String[][] arr = new String[n][n];
		for(int i = 0; i<n;i++) Arrays.fill(arr[i], " ");
        
        // 재귀 함수 
		star(0,0, m, arr);	

		//출력 
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++ ) {
				sb.append(arr[i][j]);	
			}
			sb.append("\n");
		}
		System.out.print(sb);
	}
	
    	// 재귀 함수 
	public static void star(int x, int y,int d, String[][] arr) {
    	//d==0일 때 별표 찍기 
		if(d==0) {
			arr[x][y] = "*";
			return;
		}
        //재귀 호출 
		int a = (int)Math.pow(3, d-1);
		star(x,y,d-1,arr);
		star(x+a,y,d-1,arr);
		star(x+2*a,y,d-1,arr);
		star(x,y+a,d-1,arr);
		star(x,y+2*a,d-1,arr);
		star(x+a,y+2*a,d-1,arr);
		star(x+2*a,y+a,d-1,arr);
		star(x+2*a,y+2*a,d-1,arr);
	}
}