📝 Baekjoon 2447 문제풀이
💡문제 정의
문제는 위와 같다. 재귀를 이용하는 문제!
재귀는 설명을 들을 때는 오호라... 하면서 이해가 되긴 된다 (100퍼센트 이해가 안 될 때도 있음). 하지만 관련 문제만 보면 머리가 하얘진다. 이걸 코드로 어떻게 구현하는 거지...? 생각이 머릿속을 지배. 이리 굴려도 저리 굴려도 구현하기가 쉽지 않은 것 같아서, 재귀를 표적으로 삼고 어젯밤부터 문제를 몇 개 풀어보았다.
미루고 미루던 ps 문제풀이를 한두달 전부터 깔짝대기 시작했는데, 구글링을 해보면서 깨달은 점이 한 가지 있다.
- 문제를 풀 때 시간 제한을 두자.
- 제한시간 안에 풀지 못한 문제는 미련을 갖지 말고 돌아서라. 해결한 이들의 해법을 보며 이해하고, 공부하자.
- 비슷한 유형의 문제가 있다면 꼭 풀어보고 그 해법 및 접근법을 나의 것으로 만들자.
사실 저번 달까지만 해도 안 풀리는 문제를 2-3시간씩 잡고 있었다. 하지만 언젠간 방법을 생각해낼 수 있으리라... 하며 머리를 쥐어싸매도 답은 쉽게 나오지 않는다. 아직 알고리즘 공부를 제대로 해보지도 않았는데 풀리지 않는 문제를 가지고 시간 허비를 많이 한 것 같다 ㅠㅠ
이번 달 들어서부터는 위의 3가지 법칙을 지키며 조금씩 공부를 하는 중이다. 스트레스도 훨씬 덜 받고, 새롭게 얻는 지식도 많아지는 것 같다.
어쨌든 각설하고!!! 아래는 모두 재귀를 이용하는 문제.
이 문제도 위의 세 문제와 거의 동일한 로직으로 해결했다.
1-1) C
# include <stdio.h>
char square[7000][7000];
void PrintStar(int row, int col, int n) {
int surround = n / 3;
int rowCnt = 0, colCnt = 0;
for (int i = row;i < row + n;i++) {
rowCnt++;
for (int j = col;j < col + n;j++) {
colCnt++;
if (((surround < rowCnt) && (rowCnt < surround*2+1)) &&
((surround < colCnt) && (colCnt < surround*2+1))) {
square[i][j] = ' ';
}
else if (square[i][j] != ' '){
square[i][j] = '*';
}
}
colCnt = 0;
}
if (n == 3)
return;
else {
int size = n/3;
PrintStar(row, col, size);
PrintStar(row, col+size, size);
PrintStar(row, col+size*2, size);
PrintStar(row+size, col, size);
PrintStar(row+size*2, col, size);
PrintStar(row+size, col+size, size);
PrintStar(row+size, col+size*2, size);
PrintStar(row+size*2, col+size, size);
PrintStar(row+size*2, col+size*2, size);
}
}
int main(void) {
int n;
scanf("%d", &n);
PrintStar(0, 0, n);
for (int i = 0;i < n * n;i++) {
printf("%c", square[i/n][i%n]);
if ((i+1) % n == 0) {
printf("\n");
}
}
return 0;
}n이 9라면, 3(n/3)개의 별들이 주위를 감싸고, n이 3이라면, 1(n/3)개의 별들이 주위를 감싼다. 가운데 부분은 (n/3) * (n/3) 크기 크기의 정사각형이 공백으로 채워져 있다.
rowCnt, colCnt를 이용해 가운데 부분은 공백을 넣도록, 그 주변은 모두 '*'로 채우도록 했다.
그런데 다른 사람들의 해법을 찾아보니 훨씬 간결한 것 같았다! 나는 먼저 풀었던 2630, 1780, 1992번의 해법에 익숙해져 있어서 똑같은 방법으로만 생각했는데, 굳이 전역변수를 선언하고 코드를 길게 만들 필요가 없었다.
1-2) C
# include <stdio.h>
int PrintStar(int x, int y, int n) {
if ((x / n) % 3 == 1 && (y / n) % 3 == 1) {
printf(" ");
}
else {
if (n == 1)
printf("*");
else
PrintStar(x, y, n / 3);
}
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
PrintStar(i, j, n);
}
printf("\n");
}
return 0;
}좌표 하나하나를 함수에 넘기면서, 그 안에서 함쉬 재귀호출 -> 공백을 출력할지, 별을 출력할지 조건 검사!
공백을 출력하는 좌표를 보면
(1, 1) (1, 4) (1, 7)
(4, 1) (4, 4) (4, 7)
등이 있는데, n=9라고 했을 때 이 좌표를 가지고 함수를 호출하면
(1, 1, 9) (1, 4, 9) (1, 7, 9)와 같은 형태가 된다.
이 좌표들의 공통점은 x, y를 3으로 나누었을 때 나머지가 1이라는 점.
하지만 이 조건들만으로는 부족하다.
n=9라고 했을 때,
(3, 3) (3, 4) (3, 5)
위와 같은 좌표에도 공백이 들어가야 한다 (가운데 (n/3) * (n/3) 크기의 공백 부분). 따라서 이 좌표들 또한 '3으로 나눈 나머지가 1'이라는 조건에 부합시켜야 한다.
따라서 x % 3 == 1이 아니라, (x / n) % 3 == 1으로 조건을 수정하면 공백을 출력하는 두 가지 케이스를 모두 포함할 수 있다.
만약 (x / n) % 3 == 1 && (y / n) % 3 == 1 조건을 만족시키지 않는다면
1) 재귀 호출
2) 별 출력
2가지 케이스 중 하나를 선택해야 하는데, 이 둘을 구분하는 조건문이 필요하다.
n이 1이 될 때까지 재귀호출을 했는데 (x / n) % 3 == 1 && (y / n) % 3 == 1을 만족시키지 않았다면 별을 출력해야 한다. 만약 n이 1이 되었는데 별을 출력하지 않고 계속 재귀 호출을 반복한다면, PrintStar(4, 2, 0)과 같이 n이 0이 된 상태로 재귀 호출을 하게 될 텐데, n은 0이 되면 안 된다. 따라서 별을 출력하고 재귀 호출을 종료해야 한다.
사실 1-2 부분은 코드를 보면서 끼워맞추기 식으로 이해를 한 거라, 혼자 구현을 하라고 하면 완벽하게 하지 못할 것 같다. 계속 생각해보고, 비슷한 문제도 찾아봐야겠다.
💡참고
https://velog.io/@kimmainsain/C%EC%96%B8%EC%96%B4-%EB%B0%B1%EC%A4%80-2447-%EB%B3%84-%EC%B0%8D%EA%B8%B0-10
https://patiencelee.tistory.com/747
