[알고스팟] 삼각형 위의 최대 경로

문제 링크

삼각형 위의 최대 경로

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • TRIANGLEPATH
  • 5000ms
  • 65536kb
  • 5166
  • 2592 (50%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

6
1  2
3  7  4
9  4  1  7
2  7  5  9  4

위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 삼각형의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에는 각 1개~n개의 숫자로 삼각형 각 가로줄에 있는 숫자가 왼쪽부터 주어집니다. 각 숫자는 1 이상 100000 이하의 자연수입니다.

출력

각 테스트 케이스마다 한 줄에 최대 경로의 숫자 합을 출력합니다.

예제 입력

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

예제 출력

28
341

여뗳게 풀까?

현재 위치에서의 최댓값에서 계속 다음 위치로의 최댓값을 갱신해 나가면 풀 수 있습니다.

그림의 예를 통해 어떻게 문제가 해결되는지 확인해봅시다.

코드로는 어떻게 표현할 수 있을까요?

현재 위치의 값을 memoi[y][x] 라고 한다면,

다음 위치의 값 memoi[y + 1][x] 은 memoi[y + 1][x]와 memoi[y][x] 중 큰 값과 삼각형에 들어있는 triangle[y + 1][x] 을 더한 값이 됩니다.

이는,  memoi[y + 1][x + 1]에서도 마찬가지입니다.

코드

#pragma once
#include<cstdio>
#include<cstring>
 
int triangle[101][101];
int memoi[101][102], n;
 
int max(int i1, int i2)
{
    return i1 > i2 ? i1 : i2;
}
 
void init()
{
    scanf("%d\n", &n);
 
    memset(memoi, 0, sizeof(memoi));
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            scanf("%d\n", &triangle[i][j]);
            memoi[i][j] += triangle[i][j];
            memoi[i + 1][j] = max(memoi[i][j], memoi[i + 1][j]);
            memoi[i + 1][j + 1] = max(memoi[i][j], memoi[i + 1][j + 1]);
        }
    }
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    while (t--)
    {
        init();
 
        int res = memoi[n][1];
        for (int i = 2; i <= n; i++)
        {
            res = max(res, memoi[n][i]);
        }
        printf("%d\n", res);
    }
    return 0;
}

여담

생각보다 그림 올리는게 되게 손이 많이 갑니다. 하지만 그림이 있기에 더 이해하기 쉬울것이라고 믿어 의심치 않습니다!

이왕 문제 풀이를 쓰는 김에 확실하게 쓰겠습니다!