ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준(BOJ) 1932번 정수 삼각형
    알고리즘 풀이/백준(Boj) 2019. 7. 15. 23:56

    문제 : https://www.acmicpc.net/problem/1932







    위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

    맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

    삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.


    나의풀이 :


    삼각형을 왼쪽으로 다 붙여서 직각삼각형으로 시작하자.

    y = 0 , x =0 에서 출발하여 바로 아래 ( y= 1, x =0 ) 과 대각선 ( y =1 , x =1 ) 로 나아 갈 수 있게끔 재귀함수를 호출해준다.

    n이 500이니 하나의 시작에서 갈 경우의 수는 2가지 임으로  2 ^ (500-1) 승의 경우의수가 나오고 완전 탐색으로는 접근이 불가능하다. 

    동적 계획법을 통해 중복을 없애주자.


    코드 ( C++ )


    #include <iostream>

    #include <algorithm>

    #include <cstring>

    using namespace std;

    int N;

    const int MAX = 500 + 1;

    int triangle[MAX][MAX];

    int cache[MAX][MAX];

    int solve(int y, int x)

    {

    if (y ==N-1) return triangle[y][x];

    int& ret = cache[y][x];

    if (ret != -1)

    return ret;

    ret = max(solve(y + 1, x),solve(y + 1, x + 1)) + triangle[y][x]; // 2가지 경우의수중 더 큰 수와 자기 자신을 합쳐서 기록한다.

    return ret;

    }

    void Init() {

    for (int i = 0; i <= N; ++i)

    for (int j = 0; j <= i; ++j)

    cache[i][j] = -1;

    }

    int main()

    {

    cin >> N;

    Init();

    for (int i = 0; i < N; ++i)

    for (int j = 0; j <= i; ++j)

    cin >> triangle[i][j];

    int ans =solve(0, 0);

    cout << ans << endl;

    return 0;

    }





    '알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글

    백준(BOJ) 2156번 포도주 시식  (0) 2019.07.16
    백준(BOJ) 10026번 적록색약  (0) 2019.07.16
    백준(BOJ) 2193번 이친수  (0) 2019.07.15
    백준(BOJ) 1969번 DNA  (0) 2019.07.15
    백준(BOJ) 1003번 피보나치 함수  (0) 2019.07.11
Designed by Tistory.