삼각형 위의 최대 경로 (난이도: 하)

1. 문제 설명

(1) 아래의 그림과 같이 삼각형으로 배치된 자연수들이 있다고 가정한다.

 

 

(2) 맨 위의 숫자에서 시작해서, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄까지 닿는 경로를 만들려고 한다.

* 경로는 아래줄로 내려갈 수 있으며 오른쪽과 아래의 숫자로 갈 수 있습니다.

 

 

(3) 이때 모든 경로 중 숫자의 합을 최대화하는 경로들에 포함된 숫자들의 합은 얼마인지 찾아내는

프로그램을 작성하시오.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)

(2) 그 후 두 번째 줄에 삼각형의 크기 N(1<=N<=10)

(3) 그 후 각 줄에 triangle(1<=triangle<=100)을 초기화

 

출력 조건

(1) 모든 경로 중 숫자의 합을 최대화하는 경로들에 포함된 숫자들의 합

 

 

입력 예제

2
5
6 0 0 0 0
1 2 0 0 0
3 7 4 0 0
9 4 1 7 0
2 7 5 9 4
5
1 0 0 0 0
2 4 0 0 0
8 16 8 0 0
32 64 32 64 0
128 256 128 256 128

 

출력 예제

28

341

 

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) 맨 밑층(N-1)까지 도달할 경우

 

 

 

 

6. 코드 및 풀이

: 두 가지 코드가 존재한다.

 

먼저 (1)에서는 가장 단순하게 완전 탐색으로 접근한다.

 

즉, 다 하나하나 경로를 만들어서 합이 최대화인 것을 고르는 것이다.

 

그러나, 만약 N개의 가로줄이 있을 때 가능한 경로의 수는 2^N-1이 되는데, 이는 n이 100 된다면

도저히 계산할 수 없게 될 것이다.

 

 

그러므로 (1)에서는 3차원 배열의 캐시를 사용하여 적용할 것이다.

* [y][x][sum]인데 [y][x]의 위치마다 sum값이 틀리기 때문에 3차원 배열이 필요하다.

 

 

 

(1) 완전 탐색 (3차원 캐시 적용)

public class TRIANGLEPATH1 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    // 각각 삼각형의 크기 변수와 삼각형 안의 숫자 변수
    private static int N;
    private static int[][] triangle;

    private static int[][][] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101][101][999*10+1];
            N = Integer.parseInt(sc.readLine());
            triangle = new int[N][N];

            for(int y=0; y<N; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0; x<N; x++) {
                    triangle[y][x] = Integer.parseInt(st.nextToken()); 
                }
            }
            sb.append(solve(0,0,0)+"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int y, int x, int sum) {
        if(triangle[y][x] == 0) return 0;

        // 기저 사례(1): 맨 밑층(N-1)까지 도달할 경우
        if(y==N-1) return sum + triangle[y][x];

        if(cache[y][x][sum] != 0) return cache[y][x][sum];

        int ret=0;
        sum += triangle[y][x];
        ret = Math.max(solve(y+1, x, sum), solve(y+1, x+1, sum));

        return cache[y][x][sum] = ret;
    }
}

 

 

 

그러나, 위 (1) 코드에서의 캐시를 보면 3차원 배열로 상당히 많은 메모리를 사용하고 있다는 것을 알게 된다.

 

또한 특정 입력에 대해서는 캐시가 잘 작동하지 않는 다는 것이다.

* 그 이유는 같은 위치여도 서로 다른 합일 가능성이 크기 때문

 

 

그러므로 더 빠르게 작동할려면 재귀 함수의 입력을 아래의 두 가지 부류로 나눠보면 얻을 수 있다.

1	y와 x는 재귀 호출이 풀어야 할 부분 문제를 지정한다. 이 두 입력이 정해지면 앞으로 우리가 만들 수 있는 경로들이 정해진다. 따라서 이들은 앞으로 풀어야 할 조각들에 대한 정보를 주는 입력이다.
2	sum은 지금까지 어떤 경로로 이 부분 문제에 도달했는지를 나타낸다. sum은 지금까지 풀었던 조각들에 대한 정보를 주는 입력이다.

 

 

쉽게 얘기하면 아래의 그림에서 왼쪽은 sum을, 오른쪽에는 (y,x)를 보여줘야 한다는 것이다.

 

 

이때 sum을 입력받지 않도록 하면 훨씬 빨라지게 된다.

 

단, 입력 받지 않는다면, 이전까지 어떤 숫자를 만났는지 알 수 없기 때문에 전체 경로의 최대 합을 반환할 수 없다.

 

 

그러므로 함수의 반환 값을 전체 경로의 최대치가 아니라 (y,x)에서 시작하는 부분 경로의 최대치로 바꾼다.

 

 

아래의 코드 (2)를 보고 이해하자.

 

 

 

(2) 메모제이션

public class TRIANGLEPATH2 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    // 각각 삼각형의 크기 변수와 삼각형 안의 숫자 변수
    private static int N;
    private static int[][] triangle;

    private static int[][] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101][101];
            N = Integer.parseInt(sc.readLine());
            triangle = new int[N][N];

            for(int y=0; y<N; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0; x<N; x++) {
                    triangle[y][x] = Integer.parseInt(st.nextToken()); 
                }
            }
            sb.append(solve(0,0)+"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int y, int x) {
        if(triangle[y][x] == 0) return 0;

        // 기저 사례(1): 맨 밑층(N-1)까지 도달할 경우
        if(y==N-1) return triangle[y][x];

        if(cache[y][x] != 0) return cache[y][x];

        int ret=0;
        ret = triangle[y][x] + Math.max(solve(y+1, x), solve(y+1, x+1));

        return cache[y][x] = ret;
    }
}

 

 

 

 

7. 점화식

: 점화식은 위 코드 (1)과(2) 두 개가 존재한다.

 

(1) 완전 탐색 (3차원 캐시 적용)

( 점화식은 아래칸으로 내려갔을 때 기준으로, 바로 아래칸을 선택했을 때와 오른쪽 칸을 선택했을 때를 의미한다. )

 

 

 

(2) 메모제이션

 

 

 

 

8. 생각해보기

- 효율적인 동적 계획법 알고리즘을 적용하기 위해 아주 중요한 조건은 최적 부분 구조(optimal substructure)를 

가질 수 있는지 없는지에 따라 나뉜다.

* 최적 부분 구조란, 어떤 문제와 분할 방식에 성립하는 조건이다.

 

- 즉, 부분 문제를 최적으로 풀 수 있다면, 전체 문제의 최적해를 알 수 있는 것이다.

 

- 예를 들어, 서울에서 부산으로 가는 최단 경로를 얻는 문제가 있다고 가정하자. 경로는 (서울 - 대전)과 

(대전 - 부산)으로 나뉜다고 가정하면, 두 구간의 최단 경로를 찾아서 둘을 이으면 서울에서 부산으로 가는

최단 경로를 얻을 수 있을 것이다. 이렇게 되면 이 문제는 부분 문제의 최적해가 전체 문제의 최적해로 이어지기

때문에 최적 부분 구조를 가지고 있다.

 

- 다른 예로, 서울에서 부산으로 향하는데 고속도로의 통행료 합이 3만원을 초과하지 않는 최단 경로를 얻는

문제가 있다고 가정하자. 대전에서 부산으로 가는 경로가 아래 A,B가 존재한다.

 

A: 통행시간 - 2시간, 통행료 - 1만원

B: 통행시간 - 1시간, 통행료 - 2만원

 

- A는 시간이 많이 드는 대신에 통행료 싸고, B는 시간이 적게 드는 대신에 통행료가 비싸다. 그렇다면, 이

둘의 경로를 선택하는 최적의 해는 앞 경로 (서울 - 대전)에 있는 것이다. 만약 앞 경로 (서울 - 대전)에서

통행료가 많이 나오면 A를, 적게 나오면 B를 선택할 수 밖에 없다. 이렇게 되면 이 문제는 부분 문제의

최적해가 전체 문제의 최적해로 이어질 수 없기 때문에 최적 부분 구조를 가질 수 없다.