-
백준(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