algospot TRIANGLEPATH

문제 링크입니다: https://algospot.com/judge/problem/read/TRIANGLEPATH

http://jaimemin.tistory.com/316에서 동일한 문제를 풀었지만 이번에는 재귀함수가 아닌 반복 동적 계획법을 이용해 문제를 풀었습니다.

그 결과, 재귀함수를 사용했을 때보다 실행속도가 빨라진 것을 확인할 수 있었습니다.

/*

삼각형으로 배치된 자연수들이 있다.(정사각을 왼쪽 위에서 오른쪽 아래 대각선 기준으로 잘랐을 때 아래 부분)

맨 위의 숫자에서 시작해서, 한번에 한 칸씩 아래로 내려가

맨 아래 줄까지 닿는 경로를 만들려고 한다.

경로는 아래줄로 내려갈 때마다 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있다.

이 때 모든 경로 중 숫자의 합을 최대화하는 경로는?

또한 경로에 포함된 숫자들의 최대 합은 얼마인가

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

int height; //삼각형의 높이

int triangle[100][100]; //삼각형의 표현을 위해

int cache[100][100];

int cache2[2][10000]; //슬라이딩 윈도우 기법 위한 캐시

 

/*

int iterative(void) //재귀가 아닌 반복적 동적 계획법

{

        //기저 사례를 계산(밑변 길이)

        for (int x = 0; x < height; x++)

               cache[height - 1][x] = triangle[height - 1][x];

        //다른 부분 계산(재귀함수 사용하지 않아도 됨)

        for (int y = height - 2; y >= 0; y--) //밑에서 2층 길이부터 계산

               for (int x = 0; x < y + 1; x++)

                       cache[y][x] = max(cache[y + 1][x], cache[y + 1][x + 1]) + triangle[y][x];

        return cache[0][0];

}

*/

 

//cache[i]를 계산하기 위해선 cache2[i+1]만 필요

int iterative2(void)

{

        //기저 사례 계산

        for (int x = 0; x < height; x++)

               cache2[(height - 1) % 2][x] = triangle[height - 1][x];

        //다른 부분 계산

        for (int y = height - 2; y >= 0; y--)

               for (int x = 0; x < y + 1; x++)

                       cache2[y % 2][x] = max(cache2[(y + 1) % 2][x], cache2[(y + 1) % 2][x + 1]) + triangle[y][x];

        return cache2[0][0];

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 0 || test_case>50)

               exit(-1);

 

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

        {

               //memset(cache, -1, sizeof(cache)); //캐시 초기화

               memset(cache2, -1, sizeof(cache)); //캐시 초기화

               cin >> height;

               if (height < 2 || height > 100)

                       exit(-1);

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

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

                       {

                              cin >> triangle[i][j];

                              if (triangle[i][j] < 1 || triangle[i][j]>100000)

                                      exit(-1);

                       }

               //cout << iterative() << endl << endl;

               cout << iterative2() << endl << endl;

        }

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략