[백준]2448-별찍기 - 11

방학을 시작하고 매일 백준을 풀기 시작했다. 일단 단계별로 푸는 문제를 하고있는데, 매일 대략 8문제정도를 푸는 것 같다.

며칠동안은 막힘없이 풀었는데, 이 2448번에서 갑자기 막혀 건너뛰고 문제를 풀고 있었다.

그런데 이게.. 

이렇게 중간에 도전중이 안없어지고 있는게 너무 거슬려서.. 오늘은 어떻게든 풀어보려고 했다.

문제를 처음 봤을 때 문제라고 생각했던 것이 뭐냐면,

"대충 어떤 식으로 규칙이 있는지는 알겠는데, 한 줄씩 출력하는 콘솔에서 이걸 어떻게 구현하지.."였다.

구글링을 하니 엄청나게 큰 배열을 만들어서 문제를 푸는 분들이 많으셨는데.. 흐음.. 그렇게 풀면 뭔가 맘에 안들어서.. 다른 방식으로 풀어보려고 한다.

이러다가

뒤집어봤다.

호오.. 뭔가 훨씬 쉬워보인다.

입력받은 수에 맞춰 배열을 동적할당 한 다음, 위와 같은 식으로 배열을 채워넣은 다음 역순으로 출력하면 되지 않을까 생각이 들었다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
int Rt2mul(int num, int value);
 
int main() {
    int size;
    scanf("%d", &size);
 
    char **ary = (char **)malloc(sizeof(char *) * size);
    for (int i = 0; i < size; i++) {
        ary[i] = (char *)malloc(size * 2);
        memset(ary[i], ' ', size * 2);
    }
 
    strncpy(ary[0], "*****", 5);
    strncpy(ary[1], " * * ", 5);
    strncpy(ary[2], "  *  ", 5);
 
    for (int i = 0; i < log2(size / 3); i++) {
        for (int j = 0; j < Rt2mul(i, 3); j++) {
            strncpy(&ary[j][Rt2mul(i, 6)], ary[j], Rt2mul(i, 6) - 1);
            strncpy(&ary[j + Rt2mul(i, 3)][Rt2mul(i, 3)], ary[j], Rt2mul(i, 6) - 1);
        }
    }
    for (int i = 0; i < size; i++)
        ary[i][size * 2 - 1] = '\0';
 
    for (int i = size - 1; i >= 0; i--)
        printf("%s\n", ary[i]);
    return 0;
}
 
int Rt2mul(int num, int value) {
    int sum = value;
    for (int i = 0; i < num; i++)
        sum *= 2;
    return sum;
}

일단 이게 최종 결과물이다. 하나 하나 설명하자면..

위에서 도형을 뒤집은 것을 기본으로 가정한다. 어차피 마지막에 역순으로 출력하면 되기 때문에, 역삼각형을 먼저 만들기로 한다.

가장 기본적으로 구성되는 모양이 코드의 18~20줄에 있는 역삼각형인데, 입력되는 숫자는 3 * 2^k로 제한되고, 이로 인해 입력되는 숫자는 3, 6, 12, 24, 48...등이다.

기본적으로 3이 입력되면 위의 저 작은 삼각형이고, 6이 입력되면 한 칸을 띄고 저 삼각형을 그대로 오른쪽에 붙인 후, 복사한 삼각형과 원래의 삼각형 사이 바로 아래에 또 삼각형을 복사한다. 그렇게 하면

***** *****

 * *   * *

  *     *

   *****

    * *

     *

위와 같은 도형이 나온다.

숫자가 커질수록 이와 같은 복사가 계속해서 일어나는데, 그림으로 표현하면

(발퀄 죄송합니다...)

위와 같이 복사가 진행된다는 것이다.

그렇다면 복사는 어떤 식으로 진행할 것인가?

이걸 생각하려면 먼저 입력되는 숫자에 따른 도형의 크기와 도형을 복사할 위치에 대해 정확히 알고 있어야 한다.

3일때는 복사를 할 필요가 없고, 6일 경우에는 우측으로 복사할 때 처음부터 5문자를 [행][6]에 복사하면 된다.

그 후 [3][3]부터 [4][3], [5][3]까지 그대로 똑같이 5문자를 복사하면 된다.

12나 24, 48과 같이 더 큰 숫자는 조금만 더 개념을 파악하며 생각하면 된다.

여튼 이렇게 파악을 하면 규칙이 있는데, 우측으로 복사할 때에는 6 12 24 48 등 6부터 2배로 늘어난다는 것이고,

아래로는 3 6 12 24 등 3부터 2배로 늘어난다는 것이다.

음..

쓰다보니 너무 자세해지는 것 같다.

이 정도 설명했으면 코드를 보며 스스로 이해하는 것도 필요하다고 생각하기 때문에!(라고 쓰고 귀찮다고 읽는다.)

이만 이 포스팅은 줄이기로 하는데..

마지막으로 한 가지 내가 어어어어어엄청난 시간을 잡아먹은 실수가 하나 있었다.

    char **ary = (char **)malloc(sizeof(char *) * size);

바로 이것..

처음에는 사이즈 할당을 그냥 size로 했었다.

그런데 3을 넣어도 가끔 에러가 뜨고.. 6은 되는데 12를 넣어도 6과 똑같이 나오고..

으아아아... 머리 터질 뻔 하다가 찾아냈습니다..

"포인터의 크기는 꼭 sizeof연산을 통해서.."....

허허.. 1바이트에 주소를 집어넣으려 하니 프로그램이 터지죠..

호호.. 저같은 실수 안하시길 바랄께요..