백준 2448번
오늘 풀어본 문제는 백준의 2448번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
입력
첫째 줄에 $N$ 이 주어진다. $N$ 은 항상 $3 \times 2k$ 수이다. $(3, 6, 12, 24, 48, \cdots)$ ($0 \leq k \leq 10$, $k$ 는 정수)
출력
첫째 줄부터 $N$ 번째 줄까지 별을 출력한다.
예제 입력 1
24
예제 출력 1
*
* *
*****
* *
* * * *
***** *****
* *
* * * *
***** *****
* * * *
* * * * * * * *
***** ***** ***** *****
* *
* * * *
***** *****
* * * *
* * * * * * * *
***** ***** ***** *****
* * * *
* * * * * * * *
***** ***** ***** *****
* * * * * * * *
* * * * * * * * * * * * * * * *
***** ***** ***** ***** ***** ***** ***** *****
풀이과정
1번째 시도
별 찍기 문제는 내가 처음에 코딩을 배울 때 했던 문제였는데, CLASS 4에서 만나게 되어 반갑기도 하면서도 심히 걱정되었다. 별을 도대체 어떻게 찍어야 골드 문제이면서 CLASS 4 문제일 수 있나 싶었기 때문이었다.
불안한 예감을 사실로 다가왔고 정체불명의 도형을 눈으로 목격하게 되었다. 우선 예제를 천천히 분석해본 결과 단위 삼각형을 합쳐 거대한 삼각형을 완성하는 구조라는 것을 알 수 있었다.
처음에 시도하려했던 방식을 재귀함수를 이용해 하나씩 출력하고 커서의 위치를 이동하는 방식이었다. 하지만 그런 기능은 없었다.
결국 선택한 방법은 커서 이동 대신 2차원 배열에 별을 찍을 위치를 저장하고 마지막에 이 배열을 순회하면서 전체 도형을 출력하는 방식으로 진행하기로 했다.
삼각형의 크기와 위 꼭대기 지점의 좌표를 인자로 받는 starSet 함수를 재귀함수의 형태로 구현하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
char board[10000][10000] = { 0, };
void starSet(int size, int row, int column);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
starSet(N / 3, 0, N - 1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < 2 * N + 1; j++) {
if (board[i][j] == '*') {
cout << "*";
}
else {
cout << " ";
}
}
cout << "\n";
}
return 0;
}
void starSet(int size, int row, int column) {
if (size == 1) {
board[row][column] = '*';
board[row + 1][column - 1] = '*'; board[row + 1][column + 1] = '*';
board[row + 2][column - 2] = '*'; board[row + 2][column - 1] = '*'; board[row + 2][column] = '*'; board[row + 2][column + 1] = '*'; board[row + 2][column + 2] = '*';
}
else {
starSet(size / 2, row, column);
starSet(size / 2, row + 3 * size / 2, column - 3 * size / 2);
starSet(size / 2, row + 3 * size / 2, column + 3 * size / 2);
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
사실 이 문제를 처음 접했을 때 좀 겁을 먹었었다. 뭔가 알듯말듯 한데 바로 딱 떠오르는 방법이 없었기 때문이다. 생각보다 시간이 오래걸리지 않아 다행이라는 생각이 들었다.
나중에 ‘별 찍기 - 804’ 이런 이름의 다이아나 루비 문제를 만나게 되는 것은 아닌가 궁금해지기도 한다.
(방금 솔브닥에서 찾아보고 왔는데 그런 문제는 없었다. 별 찍기 문제의 최고 난이도는 골드 4인 것이 확인되었다.)
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2448