[백준 / BOJ] 2447번 별 찍기 - 10 (C++, Python)

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

2447번: 별 찍기 - 10

---

문제

---

문제 풀이

어려운 문제다. 재귀에 대한 완전한 이해가 있어야 풀 수 있는 문제인 것 같다.

 

C++과 파이썬의 풀이가 살짝 다르지만 이번 문제는 모든 분이 C++ 상세 풀이를 보시면 도움이 될 것 같습니다.

 

C++ 상세 풀이

정답률이 52%지만, 수학적 발상이 있어야 하는 문제다. 어차피 재귀적으로 풀어야 하는 문제이므로 N = 3일 때와 N = 9일 때를 보자.

 

N = 3일 때,

(1,1)이 비어있는 것을 볼 수 있다.

 

N = 9일 때,

(1,1), (1,4), (1,7), (4,1) ... 등등이 비어있는 것을 볼 수 있다.

 

여기서 알 수 있는 점은, 1, 4, 7 순서대로 계속 비어있다는 것과 012, 345, 678로 묶어서 생각했을 때 여기서도 중앙 부분인 345가 비어있다는 것이다.

 

1, 4, 7은 i % 3 == 1, j  % 3 == 1로 일반화 할 수 있다.

또한 가운데 공백은 (i / N) % 3 == 1, (j / N) % 3 == 1로 일반화할 수 있고, 이는 위의 경우도 포함한다.

 

또한 이 문제를 재귀적으로 해결하기 위해서는 점이 찍히는 조건이 있어야 한다.

현재 정사각형의 크기가 9라고, 즉 N이 3이라고 가정하면 탐색할 수 있는 공백이 있어 (i % 3 == 1 && j  % 3 == 1) 조건에 걸릴 것이다. 여기서 N이 1이면 탐색할 수 있는 공백이 없으므로 그대로 *을 출력하면 될 것이다. 이를 재귀적으로 구현하기 위해

 

i) ((i / N) % 3 == 1 && (j / N) % 3 == 1) 일 때 공백

ii) N == 1일 때 *

 

위 두 조건에 모두 만족하지 않았을 때 다시 한번 N / 3을 매개변수로 넣어 공백이 없을 때까지 재귀할 수 있도록, *을 그릴 수 있도록 구현하였다.

 

 

void solution(int i, int j, int N) {
    if ((i / N) % 3 == 1 && (j / N) % 3 == 1)  // 이 조건일 때 빈칸
        cout << " ";
    // 이미 위 조건에서 걸러진다는 것은 별이 찍혀야 한다는 의미인데, 이 문제를
    // 재귀적으로 해결하기 위해서는 재귀 조건이 있어야 한다. 현재 정사각형의
    // 크기가 9 이상이면 (N이 3 이상이면) 탐색할 수 있는 공백이 있지만 1이라면 공백이 없으므로
    // 그대로 *을 출력한다. (N / 3 == 0과 같다)
    else if (N == 1)
        cout << "*";
    else
        solution(i, j, N / 3);
}

Python 상세 풀이

재귀는 아니지만 for문을 이용해 아예 윗줄부터 *와 공백을 그려나가도록 구현했다. 디버깅하면서 배열이 쌓여나가는 과정을 보면 이해가 쉬울 것이다.

 

def solution(arr):
    tmparr = []
    length = len(arr) # N 크기

    # 새로이 그려야 하는데, 행과 열이 3개씩 더 있으므로 3을 곱한 만큼 반복
    for i in range(3 * length):
        if i // length == 1: # 중앙에 공백을 채우기 위한 장치 (N = 9일 때 3, 4, 5 공백)
            tmparr.append(arr[i % length] + " " * length + arr[i % length])
        else: # 이외에는 그냥 출력
            tmparr.append(arr[i % length] * 3)

    return tmparr
 
arr = ["***","* *","***"]

 

C++ 코드 전문

 

Python 코드 전문

 

소감

처음으로 풀었던 골드 문제인데 참 어려웠던 것 같다.