018. Maximum Path Sum I (삼각형 모양의 수 집단에서, 최대합이 되는 경로 찾기)

 

 

​문제 (English)

By starting at the top of the triangle below and moving to admacent numbers on the row below, the maximum total from top to bottom is 23.

That is, $3+7+4+9=23$.

 

Find the maximum total from top to bottom of the triangle below:

 

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! :o)

 

Answer: 1074

문제 분석

---

한 줄씩 아래로 갈 때마다, 한 줄에 있는 원소의 개수가 하나씩 증가하는, 삼각형 모형의 수 집단이 있을 때, 가장 위 쪽에 있는 수에서 출발해서, 가장 밑에 단에 있는 수까지 이동하면서 각 수를 더할 때, 그 합이 가장 큰 경로를 찾는 문제. 이동할 때는 바로 밑에 있는 줄에서 왼쪽 혹은 오른쪽에 있는 수만을 선택해서 갈 수 있다.

 

이동하는 것에 대한 규칙성을 생각할 때, 삼각형 형태의 모양으로 생각하기보단, 아래와 같이 왼쪽 정렬을 해서 생각해 보면 그 규칙성을 발견하기가 쉽다.

 

75

95 64

17 47 82

18 35 87 10

20 04 82 47 65

19 01 23 75 03 34

88 02 77 73 07 63 67

99 65 04 28 06 16 70 92

41 41 26 56 83 40 80 70 33

41 48 72 33 47 32 37 16 94 29

53 71 44 65 25 43 91 52 97 51 14

70 11 33 28 77 73 17 78 39 68 17 57

91 71 52 38 17 14 91 43 58 50 27 29 48

63 66 04 68 89 53 67 30 73 16 69 87 40 31

04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

 

위와 같은 grid가 있을 때, 이 grid를 배열로 표현해보면, 

[0][0]

[1][0] [1][1]

[2][0] [2][1] [2][2]

...

[n-1][0] [n-1][1] ... [n-1][n-1]

 

이동하는 것을 생각해보면, 어떤 임의의 점 [r][c]에서는 [r+1][c]혹은 [r+1][c+1]로 이동할 수 있는 것

 

이런 규칙으로 이동하면서, 만나는 지점에서의 값들을 합하고, 그 합이 가장 최대가 되는 경로를 찾는 문제.

 

전형적인 다이나믹 문제이다.

 

두 가지 풀이가 가능하겠다.

 

하나는 Top-Down 형태의 식을 만들어서 푸는 것.

   g[r][c] += max(g[r-1][c-1], g[r-1][c])  

 

다른 하나는 Bottom-Up 형태의 식을 만들어서 푸는 것.

   g[r-1][c] += max(g[r][c], g[r][c+1])

풀이 1 

---

다이나믹 문제이다. 

 

Bottom-UP 방식으로 풀겠다. 이게 편하다. 이유는, Top-Down의 경우에는, c==0의 경우와, c==r의 경우를 고려해야 해서.

 

Bottom-Up 방식의 사고는 아래와 같다. 

- 제일 밑에서 하나 더 위쪽인 row에서의 한 지점에서의 최대 합은, 그 지점에서 아랫줄에 있는 양갈래 중 큰 값과의 합

- 즉, 어떤 점 g[r][c]에서의 최대합을 S(r,c)라고 하면, S(r,c) = S(r,c) + max(g[r+1][c-1], g[r+1][c])

 

문제에서 주어진 예제에서 보면, 

 

가장 밑에 있는 줄 바로 윗 줄의 값은 {2,4,6}

2에서의 최댓값 경로는, 아래 있는 {8,5}중에서 큰 값이 8과의 합. 즉 10

4에서의 최댓값 경로는, 그 밑에 있는 5와 9 중에서 큰 값인 9로의 경로. 즉 13

6에서의 최댓값 경로는, {9,3}에서의 큰 값이 9와의 합. 즉 15

 

따라서, 최대합만을 표기하면 {10, 13, 15}

 

이제 그 위에 있는 {7,4}에서 따져보면,

7에서 그 밑 수 {10,13}과의 경로에서 --> 7 + 13 = 20

4에서 그 밑 수 {13,15}와 경로를 생각하면 -> 4 + 15 = 19

 

따라서, 합은 {20, 19}

 

이제 제일 위에 있는 {3}에서 보면,

아래 있는 {20, 19}에서 20을 선택해서 -> 3 + 20 = 23

 

따라서, 답은 23이 되는 것

 

2차원 배열 형태의 수가 주어졌을 때, 위 방법으로 최댓값 합이 되는 경로를 찾는 코드는 아래와 같다.

fn find_max(mut g:Vec<Vec<u64>>) -> u64 {
    if g.len() <= 1 {return g[0][0];}

    for i in (0..=g.len()-2).rev() {
        for j in 0..=i {
            g[i][j] += get_max(g[i+1][j], g[i+1][j+1]);
        }
    }
    return g[0][0];
}

 

위 코드에서 주의할 사항은, 1줄짜리 데이터, 즉 1개 값만 주어졌을 때 처리하는 부분이다. 

if g.len() <= 1 {return g[0][0];}

 

 

문자열로 수가 주어졌을 때, 이를 2차원 배열 형태의 수로 읽어 내는 코드는,

fn read_data(s:&str) -> Vec<Vec<u64>> {
    let lines = s.trim().lines();    
    let mut g:Vec<Vec<u64>> = Vec::new();
    for line in lines {
        let v:Vec<u64> = line.split_whitespace().filter_map(|s| s.parse().ok()).collect();
        g.push(v);
    }
    return g;
}

 

전체 코드는 맨 아래 전체 소스코드 부분에서 확인.

 

hackerrank에서 동작하는 코드는 다음과 같음.

use std::io::{self, BufRead};

fn main(){
    let stdin = io::stdin();
    let mut it = stdin.lock().lines();
    let t = it.next().unwrap().unwrap().trim().parse::<i32>().unwrap();
    for _ in 0..t {
        let n = it.next().unwrap().unwrap().trim().parse::<i32>().unwrap();
        let mut vv:Vec<Vec<u64>> = Vec::new();
        for _ in 0..n {
            let v:Vec<u64> = it.next().unwrap().unwrap().trim().split_whitespace()
                        .filter_map(|s| s.parse().ok()).collect();
            vv.push(v);            
        }
        println!("{}",find_max(vv));
    }
}

fn find_max(mut g:Vec<Vec<u64>>) -> u64 {
    if g.len() <= 1 {return g[0][0];}
    for i in (0..=g.len()-2).rev() {
        for j in 0..=i {
            g[i][j] += get_max(g[i+1][j], g[i+1][j+1]);
        }
    }
    return g[0][0];
}

fn get_max(a:u64, b:u64) -> u64 {
    if a>b { return a;}
    else { return b; }
}

 

총평

---

그냥 평범한 다이나믹 문제이다.

 

전체 소스코드

---

p18.rs 

const INPUT:&str = "75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23";

const INPUT1:&str = "3";
const INPUT2:&str = "1
2 3";

#[test]
fn test(){
    let g = read_data(INPUT);
    assert_eq!(1074, find_max(g));

    let g = read_data(INPUT1);
    assert_eq!(3, find_max(g));

    let g = read_data(INPUT2);
    assert_eq!(4, find_max(g));
}

#[cfg(test)]
fn read_data(s:&str) -> Vec<Vec<u64>> {
    let lines = s.trim().lines();    
    let mut g:Vec<Vec<u64>> = Vec::new();
    for line in lines {
        let v:Vec<u64> = line.split_whitespace().filter_map(|s| s.parse().ok()).collect();
        g.push(v);
    }
    return g;
}

#[cfg(test)]
fn find_max(mut g:Vec<Vec<u64>>) -> u64 {
    if g.len() <= 1 {return g[0][0];}

    for i in (0..=g.len()-2).rev() {
        for j in 0..=i {
            g[i][j] += get_max(g[i+1][j], g[i+1][j+1]);
        }
    }
    return g[0][0];
}

#[cfg(test)]
fn get_max(a:u64, b:u64) -> u64 {
    if a>b { return a;}
    else { return b; }
}

 

끝