백준 2447번 - 별 찍기 - 10

백준 2447번 - 별 찍기 - 10

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

2447번: 별 찍기 - 10

이 문제는 재귀 알고리즘 문제이다.

 

단계별로 풀어보기 문제들 중에서 안 풀었던 문제가 있길래 풀려고 보니 별 찍기..

쉬울 거 같아서 빨리 풀어야겠다 하고 풀었는데 2시간 넘게 고민해도 답이 안 나오네??

결국 구글링을 통해 알아낸 사실은 2차원 배열을 사용하는 것!!

이 문제의 핵심은 저거였다.. 그것도 모르고 몇 시간을 고민했으니 ㅠㅠ

 

2차원 배열을 사용하면 또 바로 풀 수 있나?? 그것도 아니었다.

고민 고민하다가 많은 시도 끝에 풀 수 있었다.

 

처음에 계속 별이 제대로 안 나온 이유는 좌표를 재귀 함수로 넘겨줄 때의 방식에 오류가 있었다.

곰곰이 생각해 본 결과, 받아온 좌표와 가야 될 좌표는 연관성이 있다는 것을 알게 되었고 그래서 풀 수 있었다.

 

또 함정이 있었는데 별이 아무리 잘 찍혀도 틀리는 경우가 생긴다.(나 포함)

 

찾아보니 대부분 배열에 저장해 놓았다면 아마 2중 for문을 통해 출력할 텐데 배열에 아무것도 저장하지 않는다면

배열을 초기화할 때 NULL값(0)으로 초기화가 되어있기 때문에 출력도 NULL값으로 출력이 된다.

이때 문제의 출력에서 원하는 값은 '  '(space)이고 내 코드가 출력하는 값은 NULL값이므로 틀리게 된다.

('  ' 와 NULL은 ASCII 코드 값이 달라요!!) 

해결 방법은 아주 간단하다. 출력할 값이 NULL이면 '  '을 출력하면 된다.

 

#include <iostream>
using namespace std;
int n;
char arr[2500][2500];
void print_star(int a, int b, int x) {
    if (x == 1) {
        arr[a][b] = '*';
        return;
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == 1 && j == 1) { 
                continue;
            }
            print_star(a + (i * (x / 3)) , b + (j * (x / 3)), x / 3);
        }
    }
}
 
int main() {
    scanf("%d", &n);
    print_star(0, 0, n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == NULL) printf(" ");
            else printf("%c", arr[i][j]);
        }
        printf("\n");
    }
}

2차원 배열 때문에 고민한 내 시간이 너무 아까워!!!