[프로그래머스] 68645번 - 삼각 달팽이 (재귀함수)

1. 문제 및 예제

 

 이게 무슨 유형의 문제인가... 구현인가 싶었는데 재귀가 정답이었다. 배열에 그리는 문제를 전에 만나봐서 예외 처리 빼고는 어렵지 않게 설계할 수 있었다. 재귀함수 잘 쓰고 싶다.. 지금은 그냥 써야될 때 쓰는 수준? 책에서 본 알고리즘 풀이들은 재귀함수를 마치 무기처럼 자유자재로 쓰던데 그 경지에 도달할 때 까지 연습하고 싶다.

---

https://school.programmers.co.kr/learn/courses/30/lessons/68645

프로그래머스

 

---

2. 풀이과정

 

문제를 나누는게 참 중요하다는걸 알았지만 이 문제에서는 뼈저리게 느꼈다. 일단 나의 풀이는 하나의 삼각형을 큰 삼각형과 그 만의 삼각형으로 나누는 것이다. 그리고 굳이 문제에서처럼 정삼각형으로 만들 필요는 없다. 나는 직각처럼 구현하여 풀었다. 그래도 왼쪽에서 오른쪽으로 훑으면서 정답 배열에 추가하는 방식은 바뀌지 않으니까... 아래의 그림을 보자.

---

---

n=6일때의 삼각형인데 이렇게 큰 하나의 삼각형으로 보다가 아래처럼 삼각형을 나눠봤다.

---

---

 이렇게 보니까 규칙이 보였다. 꼭짓점을 기준으로 아래 오른쪽 대각선(위) 방향으로 하나씩 증가하는 숫자들로 채워진 것이다. 겉 삼각형을 그리고 나면, 안에 있는 삼각형을 그리면 되고, 이렇게 최종적으로 모든 삼각형을 그릴 때 까지 반복하면 된다. 자 방법을 알았으니 문제를 나눠보자.

 

[문제 나누기]
1. 입력
2. 재귀함수를 이용하여 삼각형 그리기(배열에 입력)
3. 생성된 배열을 answer 배열에 넣기

4. return

 

 가장 중요한 재귀함수는 다음과 같다.

 

void draw_triangle(int start_row, int start_col, int start_num, int size)

 

 해당 함수를 설명하자면, 꼭짓점이 start_row, start_col이고 가로와 세로의 길이가 size은 삼각형을 start_num 부터 시작해 그리는 함수이다. 물론 겉이 다 그려지면 값을 최신화하여 자신을 다시 호출한다. 다음은 정답 코드이다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int triangle[1000][1000];
int tmp = 6;

void draw_triangle(int start_row, int start_col, int start_num, int size) {

    for (int i = start_row; i < start_row + size; i++) {
        triangle[i][start_col] = start_num;
        start_num++;
    }

    for (int i = start_col + 1; i < start_col + size; i++) {
        triangle[start_row + size - 1][i] = start_num;
        start_num++;
    }
    
    int index_row = start_row + size - 2;
    int index_col = start_col + size - 2;

    while (start_row < index_row && start_col < index_col) {
        triangle[index_row][index_col] = start_num;
        index_row--;
        index_col--;
        start_num++;
    }

    if (size - 3 > 0) 
        draw_triangle(start_row + 2, start_col + 1, start_num, size - 3);
}

vector<int> solution(int n) {
    vector<int> answer;
    
    draw_triangle(0, 0, 1, n);
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            answer.push_back(triangle[i][j]);
        }
    }
    
    return answer;
}