문제 이해 단계
https://www.acmicpc.net/problem/2448
2448번: 별 찍기 - 11
첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)
www.acmicpc.net
N = 24 일 때의 출력이다.
예제를 보고 규칙을 유추하고 별을 찍는 문제
입력 N은 무조건 3 * 2^k로 들어온다.
여기서 k의 범위는 0≤k≤10이다.
문제 접근 단계
별 찍기 시리즈 문제이다.
때문에 구현문제인 것 같은데, 어떤 식으로 구현해야 할까?
k의 범위가 0부터 10까지니까 순서대로 해봤다.
이 이상은 그림이 너무 커질 것 같아서 k = 2 일 때까지만 그려보도록 하겠다.
이렇게 k가 1씩 커져갈 때의 규칙을 보면 이런 규칙이 보인다.
이렇게 삼각형으로 선을 그어보면,
k번째에 만들어진 삼각형을 3방향으로
배치하여 k+1번째의 도형을 만드는 것을 알 수 있다.
또한, 알 수 있는 점은 모든 도형은 k = 0일 때의 도형으로 이루어져 있다는 것이다.
k = 2 일 때의 도형은 k = 0일 때의 도형이 9개 배치된 것이라고도 볼 수 있다.
이를 k = 1 일 때의 관점에서 본다면?
k = 2일 때의 도형은, k = 1 일 때의 도형이 3개 배치된 것이라고도 할 수 있다.
여기서 재귀적인 특징을 확인할 수 있다.
k = 2일 때의 도형을 구하기 위해서는 k = 1일 때의 도형을 구해야 하고,
k = 1일 때의 도형을 구하기 위해선 k = 0일 때의 도형을 구해야 한다.
이 특징을 이용해서 문제를 풀 수 있다.
k = 2 일 때의 삼각형 가장 위의 꼭짓점을 중심으로 보자.
이 삼각형의 가로변과 세로변의 길이는 12이다.
여기서 k = 1 인 삼각형 3개를 만들기 위해서는
가로변과 세로변의 길이가 6인 삼각형을 3개 만들어야 한다.
이를 그림으로 보면 이렇게 된다.
먼저 검은 선의 길이가 k = 2 일 때이다.
k = 1을 구하기 위해 이를 반으로 잘라 양변이 6인 삼각형이 3개가 나오도록 한다.
마찬가지로 k = 1일 때도 동일한 과정을 반복해서 k = 0까지 간다.
여기서 네모로 표시된 부분은 재귀함수가 시작되는 중심 좌표이다.
즉 각 삼각형의 중심이 되는 부분이라고 할 수 있다.
도형이 만들어질 때 여기서부터 시작한다고 보면 된다.
우리는 위의 그림을 x, y 좌표를 통해 구현을 하면 된다.
여기서 밑변의 길이는 2*N-1이다.
이를 이용해서 네모의 좌표,
즉 도형이 만들어질 때의 시작이 되는 중심좌표를 구할 수 있다.
이를 이용해서 코드를 짜보자.
문제 구현 단계
#include <iostream>
#include <algorithm>
using namespace std;
char map[10000][10000]; // 별을 찍는 맵
// k = 0 일 때 그림을 그리는 것(최소 단위)
void unit(int sx, int sy){
map[sx][sy] = '*';
map[sx+1][sy-1] = '*';
map[sx+1][sy+1] = '*';
for(int i = sy-2; i <= sy + 2; i++) map[sx+2][i] = '*';
}
// 중심좌표를 기준으로 그림을 그림-> (sx,sy)좌표에 길이 len으로 그림
void Draw(int sx, int sy, int len){
// N = 3이면 최소단위 unit() 호출
if(len == 3){
unit(sx,sy);
return;
}
// len < 3 이면 그냥 return
else if( len < 3) return;
int halfX = len/2; // 절반으로 분할
int halfY = len/2; // 절반으로 분할
Draw(sx,sy,len/2); // 맨 위에 있는 삼각형
Draw(sx+halfX,sy-halfY,len/2); // 왼쪽 삼각형
Draw(sx+halfX,sy+halfY,len/2); // 오른쪽 삼각형
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N;
cin >> N;
int sy = (2*N-1)/2;
fill(&map[0][0],&map[9999][10000],' ');
Draw(0,sy,N);
for(int i = 0; i < N; i++){
for(int j = 0; j < 2*N-1; j++) cout << map[i][j];
cout << "\n";
}
}코드는 위와 같다. unit()은 최소단위일 때의 별을 찍는 것인데,
매개변수로 받은 (sx, sy) 좌표를 기준으로 그림을 그린다.
Draw() 함수는 위에서 얘기했던 것처럼
삼각형의 길이를 반으로 나누고, 3개로 쪼개는 것을 반복한다.
여기서 핵심은 도형이 만들어지는 중심 좌표를 정확히 계산하는 것이다.
사실 이 값에 대해서는 직접 해봐야 와닿기 때문에
코드를 참고해서 직접 해보길 바란다.
아 그리고 map을 선언해 준 뒤, 모든 map 배열을 ' '로 초기화해 주는 것을 잊지 않도록 한다.
NULL 값이 하나라도 있으면 틀렸습니다가 뜬다.
그리고 맵의 크기가 10000인 이유는, 밑변의 길이가 2*N-1까지이기 때문이다.
K = 10 -> 3 * 1024 = 3072
2 * 3072 - 1 = 6144 - 1 = 6143 이기 때문에
인덱스 초과가 뜨지 않기 위해 넉넉하게 잡아놨다.
풀이는 여기까지이다.
시행착오
인덱스 계산에서 애를 먹었고, 문제를 다 풀긴 했는데 계속 틀렸습니다가 떴다.
왜 그런지 계속 고민했는데,
결과적으로는 맵의 크기를 map [5000][5000]으로 잡은 것이 문제였다.
밑변의 길이가 5000이 넘을 수 있다는 것을 간과했다.
좀 더 고민을 많이 해야겠다.
구현문제를 좀 더 빠르게 푸는 습관을 들여야겠다.
토스아이디
toss.me