티스토리 뷰
이 문제는 단순하게 숫자를 입력받으면 위에 있는 거꾸로 된 삼각형을 출력하는 문제이다.
재귀 문제이며 규칙을 찾아야한다.
처음에는 이런 패턴인줄 알았다.
그래서 각 점의 좌표를 구하려고했다. 물론 틀렸고
이렇게 반복되는 것이고 주황 표시된 좌표를 구해야했다.
이제 문제 출력을 2차원 배열에 채워 나가자.
일단 내 뇌가 인식하기 위해서는 그림을 그려야한다. 인덱스 번호까지 적어주자.
일단 1이 입력값으로 주어지는 경우 0,0/0,1/1,1을 칠해야한다.
재귀 호출을 적어주자. 행은 x 열은 y로 적어주자.
func(x, y) 먼저 각 케이스대로 적어주면
func(x, y)
func(x, y+1)
func(x+1, y)
가 된다. 이게 근본이되는 호출이다.
그리고 우리가 기저 사례 base case를 만들어줘야한다.
이는 우리가 칠해야하는 칸의 케이스가 1인 경우 즉
size가 1이 된다.
이 코드는
if( size == 1) { board[x][y] == '*'; return; }
이 된다. 꼭 기저사례이니 탈출할 수 있도록 return을 적어줘야한다.
함수는 void 타입으로 만들거라 return만 쓴다.
이후 각 케이스에 해당하는 호출을 적어준다. 일단 먼저 우리는 케이스를 의미하는 size를 추가해줘야한다.
먼저 알아야하는 것은 문제의 행의 크기, 열의 크기는 동일하며
입력값을 2의 승으로 넣어주면 된다.그것이 배열의 행, 열의 크기다.
int n은 입력값을 넣어주고,
여기서 두가지 경우가 존재하는데
2의 제곱의 경우 쉬프트 연산으로 하냐 pow를 사용하냐 이다.
솔직히 pow 연산이 난 더 편하다.
그래도 쉬프트 연산에 익숙해지는게 좋을 것 같다.
쉬프트 연산 <<을 사용하며
우리의 경우 1부터 <<하면된다.
1 << n으로 2의 n제곱이 된다.
이제 메인에서 호출시 func(0, 0, size)의 size 값을 정해줘야한다.
1을 넣어줄 경우 n은 2가 된다.
2를 넣어주고 2를 반으로 줄여주면 1이 된다.
딱 맞는다.
더구나 노트에 적혀있는 func(0,1) func(1,0)또한 size값을 더한 것처럼 보인다.일단 해보자.
void func(int x, int y, int size){
if( size == 1) { board[x][y] = '*'; return; }
size /= 2;
func(x,y, size);
func(x,y+size, size);
func(x+size,y, size);
}
2가 입력값을 들어왔을 경우 생각해보자.
n은 4고 func(0,0,4)를 메인에서 호출시
size가 2가 되면서 0, 0, 2가 되며 그 이후 0 0 1, 0 1 1를 호출한다.
사실 왼쪽 그림 그리면서 확인해봐서 size를 더하는 게 맞다.
모든 그림의 0,0은 칠해지니까 호출은 0,0을 호출해야하는 것이다.