2448번: 별 찍기 - 11

2018.12.27.

문제 출처:

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

문제 분석:

 3×2k (k<=10)을 만족하는 N을 입력했을때 다음문제의 규칙을 출력한다.

N이 3일때는 가로5 세로3의 배열 안에

ex)

00*00

0*0*0

*****

로 들어간다.

이 때 처음 실행한 이를 f(0)이라 했을때

다음 실행하는 것은

f(0)                                f(1)

f(1)=                              f(2) = 

f(0)        f(0)                    f(1)        f(1)

이다.

이러한 모양이 반복 되서 실행된다.

문제 해결:

결과적인 해결방법은 다음과 같았다.

문제 분석 부분의 반복되는 부분을 재귀함수에 넣어주려고 했다.

첫번째 줄을 시작으로 기준점을 좌표로 잡는다.

f(N)            

f(N+1)=                        

f(N)        f(N)                

맨 위의f(N) 기준점이라 했을때 기준점으로 부터 얼마나 이동해야 좌우의 f(N)이 시작되는 기준점이 나오는지 확인한다.

f(N) = a,b라 했을때

(a+3×2k-2  , b+3×2k-2 ) , (a-3×2k-2  , b+3×2k-2 )가 각각 다음 좌우의 기준점이었다.

f(N) 이후 f(N-1), f(N-2) 반복해서 감소하여 f(0)이 됬을 때 별을 출력하면 된다.

그리고 입력받는수 3 6 12 24 48을 각각 1 2 3 4 5로 변환 시켜주어 계산에 편의를 주려했지만

여러번 시도 끝에 나중에 계산해본 결과 처음에 입력받은 값으로 전체 세로길이 전체 가로길이 기준점 등을 쉽게 해결할 수 있었다.

기준점의 좌표

(a,b) = (l-1,0)

가로 세로

마지막까지 입력받아야할 가장 긴 길이가

세로

c = l

가로

d = 2*l -1

이를 기반으로 코드를 작성

내 소스코드:

#define _CRT_SECURE_NO_WARNINGS   
#include <stdio.h>    
#include <math.h>
 
void Pibo(int num, int a, int b, char arr[3072][6144]);
 
char arr[3072][6144];
 
int main()
{
    int num;
    int a, b;
    int c, d;
    int k = 0;
    int l;
 
 
    scanf("%d", &num);
    l = num;
    num = num / 3;
    if (num > 2)
    {
        for (;num > 2;k++)
        {
            num /= 2;        
        }
        num = k + 2;
    }
    
    a = l - 1;
    b = 0;
        
    c = l;
    d = 2*l -1;
    
    for (int i = 0;i < c;i++)
    {
        for (int j = 0;j < d;j++)
        {        
            arr[i][j] = ' ';                            
        }
    }
 
    Pibo(num, a, b, arr);
 
    for (int i = 0;i < c ;i++)
    {
        for (int j = 0;j <d;j++)
        {
            printf("%c",arr[i][j]);
        }
        printf("\n");
    }
 
    return 0;
}
 
void Pibo(int num,int a, int b, char arr[3072][6144])
{
    
    if (num == 1)
    {        
        arr[b + 2][a + 2] = '*';
        arr[b + 2][a + 1] = '*';
        arr[b + 2][a ]  = '*';
        arr[b + 2][a - 1] = '*';
        arr[b + 2][a - 2] = '*';
        arr[b + 1][a + 1] = '*';
        arr[b + 1][a - 1] = '*';
        arr[b][a] = '*';
        return;
    }
    else
    {
        Pibo(num - 1, a, b, arr);
        Pibo(num - 1, a + 3 * ((int)pow(2, num -2) ), b + 3 * ((int)pow(2, num - 2)), arr);
        Pibo(num - 1, a - 3 * ((int)pow(2, num - 2)), b + 3 * ((int)pow(2, num - 2)), arr);
    }
}

실행결과:

고찰:

아직 재귀함수를 이용하는데 익숙하지가 않아서 이 문제 푸는데 시간이 오래걸렸다.

처음에 이 문제를 보고 분석할때 있었던 규칙이 점점 커지며 반복되는 것을 재귀로 생각하는데도 오랜 시간이 걸렸다.

재귀로 만들 부분도 정하고 규칙 찾기도 수십번 틀리면서 찾아내었다.

그리고 마침내 처음 생각한 방법은 int형 이차원 배열로 별이 들어갈곳을 1 나머지를 0으로 넣고 마지막에 1인 부분을 확인해서 별로 출력했지만

시간초과를 처음으로 보게되었다.

다음 방법으로 위 방법을 생각하게 되어 같은 규칙으로 char형 배열에 별을 넣어주는 방법을 선택하게 되었다.

시간초과에 관한 내용은 나중에 다시 이글을 보게 됬을때 알아봐야겠다.