문제 url:
별 찍기 - 10
문제:
🤔 문제 알아보기
지금은 타 블로그를 보면서 문제를 이해하고 풀 수 있지만, 처음에는 풀지 못하였다.
그래서 필지가 아래의 블로그를 보면서 이해한 부분을 설명하고자 한다.
[백준] 2447번 : 별 찍기 - 10 - JAVA [자바] Stranger's LAB
먼저, 필자는 이전 문제 4779번: 칸토어 집합 문제를 푼 방식과 어느 정도 유사성을 있다고 생각하여 처음에는 해당 문제 풀이와 비슷하게 접근해보았다.
하지만, 실 풀이는 다음과 같다.
해당 그림은 조건을 만족하는 가장 작은 형태의 그림이다. 만약 해당 칸에 별을 다 찍는다면, 총 9개의 별이 찍힐 것이다. 여기서 공백이 들어가는 부분은 별이 5 번째 찍히는 부분인데,
그렇다면 별을 총 9개 찍을 때, 5 번째 찍히는 공간은 별 대신 공백을 찍으면 될 것이다.
그럼 이제 해당 크기보다 큰 형태를 그려보자
크기가 인 정 사각형의 형태이다. 해당 그림도 마찬가지로, 맨 위의 그림이 5번 찍히는 공간에는 공백이 나머지는 다음과 같이 찍히는 것을 볼 수 있다.
그럼 tc인 27를 입력했을 때 나오는 그림을 알아보자,
화질이 좋지 않은점 양해바랍니다.
tc가 27인 그림 역시, 위의 그림이 총 9개 찍히는데, 5번 째 찍히는 공간은 공백으로 표시하는 것을 볼 수 있다.
그럼 이제 패턴을 분석을 해봤으니 이를 코드로 작성해보자,
해당 문제는 재귀함수를 통해, 나눌 수 없는 가장 작은 값까지 나눈 다음 합치는 분할 정복의 형식을 띈다.
🐱👤 실제 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static String[][] star;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
int N = Integer.parseInt(br.readLine());
star = new String[N][N];
print_star(0, 0, N, false);
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
sbd.append(star[i][j]);
}
sbd.append("\n");
}
System.out.println(sbd);
}
static void print_star(int x, int y, int length, boolean blank) {
if(blank) {
for(int i = x; i < x + length; i++) {
for(int j = y; j < y + length; j++) {
star[i][j] = " ";
}
}
return;
}
if(length <= 1) {
star[x][y] = "*";
return;
}
int new_length = length / 3;
int cnt = 0;
for(int i = x; i < x + length; i += new_length) {
for(int j = y; j < y + length; j += new_length) {
cnt++;
if(cnt == 5) {
print_star(i, j, new_length, true);
}else {
print_star(i, j, new_length, false);
}
}
}
}
}
😎 코드 해석 및 풀이
우리가 먼저 다시 복기해야 하는 로직이 있다.
우리가 총 9개의 별(혹은 정사각형 공간)을 찍을 것인데, 5번 째에는 별이 아닌 공백을 입력해준다는 것이다.
또한, 공백의 크기는 입력받은 N값의 /3만큼 가진다고 한다.
즉, 가로: N /3 세로: N / 3의 크기를 가진다는 얘기이다.
마지막으로 해당문제는 재귀호출을 하여 더 이상 나눌 수 없는 길이인 1까지 호출한 후 이를 합치는 분할 정복 알고리즘의 형태를 띈다는 점을 기억하면
위의 코드가 더 쉽게 이해될 것이다.
1번째 코드
int new_length = length / 3;
int cnt = 0;
for(int i = x; i < x + length; i += new_length) {
for(int j = y; j < y + length; j += new_length) {
cnt++;
if(cnt == 5) {
print_star(i, j, new_length, true);
}else {
print_star(i, j, new_length, false);
}
}
}위에서 설명했듯, 공백의 크기는 N/3을 가진다고 한다.
그래서 new_length 변수에는 현재 길이의 /3값을 가진다.
cnt 변수는 5번 째 별(혹은 정사각형 공간)을 찍을 때, 공백으로 표기하기 위한 장치로써 사용하는 변수이다.
그럼 아래 반복문을 해석해보자,
위에서 살펴봤던 TC 27를 입력받는다고 가정하자,
그럼 new_length는 9만큼 가질 것이다.
그럼 x=0, y=0의 초기값부터 시작한다면,
x가 0일 때, y는 0~ 8, 8 ~ 17, 17 ~ 26 총 3번 반복할 것이다.
x가 9일 때, y는 0~ 8, 8 ~ 17, 17 ~ 26 총 3번 반복할 것이다.
x가 18일 때, y는 0~ 8, 8 ~ 17, 17 ~ 26 총 3번 반복할 것이다.
이렇게 총 9번이 반복되는 것이다.
자, 그럼 우리가 위에서 설명했던 모양이 어떻게 생겨나는지 이제 알 것 같다.
그럼 가장 작은 정사각형을 가질 수 있는 길이가 3인 형태로 가보자,
x가 0일 때, y는 0, 1, 2 총 3번 반복,
x가 1일 때, y는 0, 1, 2 총 3번 반복,
x가 2일 때, y는 0, 1, 2 총 3번 반복,
여기서, 그러면 5번째 오는 좌표인 [1,1]은 우리가 공백을 받아야 할 것이다.
이때 cnt변수를 사용하여 조건을 부여할 수 있는 것이다.
if(cnt == 5)일 때, 이제 print_star(i, j, new_length, true); 를 호출함으로써 공백을 입력할 수 있는 것이다.
2번 째 코드
static void print_star(int x, int y, int length, boolean blank) {
if(blank) {
for(int i = x; i < x + length; i++) {
for(int j = y; j < y + length; j++) {
star[i][j] = " ";
}
}
return;
}
위에서 cnt가 5일 경우 blank에 true를 주는데,
이때 해당 로직이 동작한다.
그러면, 우리가 아까 [1,1]에서 공백을 가진다고 했는데,
print_star(1, 1, 3/3, true); 값을 입력하면,
[1,1]이 공백으로 입력되는 것을 알 수 있다.
더 나아가 가로세로 길이가 9인 정사각형인 기준을 계산해보면,
우리는 아래와 같이 반복한다고 설명을 했다.
x가 0일 때, y는 0~ 8, 8 ~ 17, 17 ~ 26 총 3번 반복할 것이다.
x가 9일 때, y는 0~ 8, 8 ~ 17, 17 ~ 26 총 3번 반복할 것이다.
x가 18일 때, y는 0~ 8, 8 ~ 17, 17 ~ 26 총 3번 반복할 것이다.
이때, cnt값이 5번이 되는 경우는 x가 8 ~ 17범위까지, y가 8 ~ 17범위까지 값을 가질 때이다.
그럼 해당 범위만큼, 공백을 가진다는 얘기이다.
3번 쨰 코드
if(length <= 1) {
star[x][y] = "*";
return;
}우리는 아까 위에서 설명했듯, 재귀 호출을 하여 더 이상 나눌 수 없는 길이 1인 상태가 될때까지 호출을 진행한다고 했다.
그렇게 길이가 1이 됐을때, 만약 cnt가 5인 경우가 아니라면 해당 좌표에 별을 찍어줘
우리가 원하는 결과를 얻을 수 있다.
🤢 회고
처음으로 풀어본 골드 문제로 생각부터 구현까지 쉽지 않았던 것 같다.
이상하게 답지를 보면 금방 이해가 되는데, 왜 첨부터 풀려고 하면 안되는지 잘 모르겠다.
규칙을 찾고 이해하는 연습은 결국 많은 문제를 풀어볼 수 밖에 없는 것 같아서 계속해서 풀어보며 감을 익히도록 해야겠다.
💜 참고자료
