250x250
Notice
Recent Posts
Recent Comments
Link
«   2024/05   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
Tags more
Archives
Today
Total
관리 메뉴

탁월함은 어떻게 나오는가?

[백준알고리즘, BOJ] 2447번 별 찍기 - 10 [C++, JavaScript] 본문

[Snow-ball]프로그래밍(컴퓨터)/Algorithm Training

[백준알고리즘, BOJ] 2447번 별 찍기 - 10 [C++, JavaScript]

Snow-ball 2022. 3. 23. 19:00
반응형

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 NxN 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)x(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

 

 

입력

첫째 줄에  N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3^k이며, 이때 1<= k < 8 이다.

 

 

출력

첫째 줄부터 N번쨰 줄까지 별을 출력한다.

 

 

 

 

 

코드 : 

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
using namespace std;
 
void star(int i, int j, int N) {
    if ((i / N) % 3 == 1 && (j / N) % 3 == 1)cout << ' ';
    else
        if (N / 3 == 0)cout << '*';
        else star(i, j, N / 3);
 
 
}
 
int main() {
 
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
            star(i, j, N);
        cout << endl;
    }
    return 0;
}
 
 cs

 

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Array.matrix = function (m, n, initial) {
  let a,
    i,
    j,
    mat = [];
  for (i = 0; i < m; ++i) {
    a = [];
    for (j = 0; j < n; ++j) {
      a[j] = initial;
    }
    mat[i] = a;
  }
  return mat;
};
 
const N = 27;
const arr = Array.matrix(N, N, 0);
main();
 
function main() {
  for (let i = 0; i < N; ++i) {
    for (let j = 0; j < N; ++j) {
      star(i, j, N);
    }
    console.log("");
  }
}
 
function star(i, j, N) {
  if (Math.floor((i / N) % 3) === 1 && Math.floor((j / N) % 3) === 1) {
    process.stdout.write(" ");
  } else {
    if (Math.floor(N / 3) === 0) {
      process.stdout.write("*");
    } else {
      star(i, j, Math.floor(N / 3));
    }
  }
}
 
 cs

 

 

 

 

 

 

풀이 :

1) 3행 3열을 기준으로만 생각해보면 공백이 들어가는 자리는 (1, 1)이다. 행과 열을 3으로 나누고 나머지가 1이 남는다면 공백을 준다.

그렇다면 식은 [(행 % 3 == 1) && (열 % 3 == 1)] > [(i % 3 == 1) && (j % 3 == 1)]로 표현할 수 있다.

 

2) 1번 풀이를 확장해서 생각해보자. 3행 8열을일 경우에도 행과 열을 3으로 나누고 나머지가 1이면 공백을 주면 된다. 

 

3) 그렇다면 8행 8열일 경우를 생각해보자. 9행 9열의 경우 3행 3열의 확장버전이다. 

9행 9열일 경우에는 (3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)가 공백이 된다.

i를 기준으로 본다면 [i / 3] 나눈값이 1이라면 공백이 된다. (j일 경우도 동일)

그러면 아래와 같이 i와 j는 크게 3단위로 나눠진다. i / 3과 j / 3 = 0, 1, 2 의 경우이다.

그렇기때문에 [(i / N) % 3 == 1 && (j / N) % 3 == 1]로 공식을 표현할 수 있게 된다. 

 

 

 

 

 

 

 

 

 

베타존 : 네이버쇼핑 스마트스토어

나를 꾸미다 - 인테리어소품 베타존

smartstore.naver.com

 

반응형

'[Snow-ball]프로그래밍(컴퓨터) > Algorithm Training' 카테고리의 다른 글

[Algorithm] 프로그래머스 햄버거 만들기  (0) 2022.11.04
[Algorithm] 욕심쟁이 알고리즘 동전 거슴름돈 문제풀이 [C++]  (0) 2022.04.17
[백준 알고리즘] 18870번 좌표 압축 [C++, javascript]  (0) 2022.03.14
[백준알고리즘] 10814번 나이순 정렬 [C++]을 안정 정렬(Stable Sort)로 풀어보자.  (0) 2022.03.09
[백준알고리즘] 1181번 단어 정렬 [C++]  (0) 2022.03.08
'[Snow-ball]프로그래밍(컴퓨터)/Algorithm Training' Related Articles more
Comments