[알고리즘 문제] Mountain

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        mountain(n);
    }

    static void mountain(int n) {
        if (n == 1) {
            System.out.print(1);
        } else {
            mountain(n - 1); // N높이 산의 왼쪽부분
            System.out.print(n); // N높이의 산을 정의 : (n-1) N (n-1)
            mountain(n - 1); // N높이 산의 오른쪽부분
        }
    }
}

문제는 위의 사진처럼 좌우대칭 모양의 산 모양(높이)을 출력하는 것이다. 

 

먼저 문제를 보면 N높이의 산은 좌우로 N-1높이의 산을 가지고 있다. 또 N-1높이의 산은 N-1보다 1씩 작은 높이의 산을 좌우로 가지고 있다.4높이의 산은 좌우로 3 높이의 산을 가지고 있고, 또 3높이의 산은 2높이의 산을, 2높이의 산은 1높이의 산을 가지고 있다. 하지만 1높이의 산은 좌우로 산을 가지고 있지 않다. 그 자체로 존재할 뿐이다.

 

N산을 출력하기 위해서는 N-1산을 출력해야 하고, N-1산을 출력하기 위해서는 N-1보다 1씩 작은 산을....이렇게 위의 문제는 재귀적인 성격을 가진다. 그렇다면 무엇을 재귀함수로 만들까 ? 기저조건까지 자기 자신을 호출하는, 재귀함수는 N높이의 산을 출력하는 기능을 하게 된다.

 

만약 N=1인 경우는 산을 표시할 필요가 없기 때문에 기저조건이 된다. 즉 재귀함수의 탈출 조건. 만약 높이가 1이 아니라면, N높이 함수의 정의 mountain(N-1) N출력 mountain(N-1)을 실행하게 된다. 

 

mountain(2), 즉 높이 2의 산을 출력하는 경우라면, 먼저 n==1이 아니므로 else문을 실행한다. 다시 mountain(2-1)을 실행하게 되고, 이 함수에서 n==1이므로 1을 출력한다. 이후 다시 System.out.println(2)를 실행하게 되고, 다시 mountain(2-1)를 실행, n==1에 걸려 1을 출력하여 결국에는 121를 출력하게 된다.

 

중요한 부분은 문제에서 재귀적인 규칙을 도출하여, 이런 규칙에 부합하는 재귀함수와 매개변수를 정의하는 것이다. 또 재귀함수를 만족하는 최소한의 조건(기저조건) 또는 탈출조건인 N=1인 경우(양 옆의 산이 없으므로 1을 출력)을 구하는 것이 이 문제 해결에 있어 중요한 부분이다.