[알고스팟] 삼각형 위의 최대 경로 개수 세기

문제 링크

삼각형 위의 최대 경로 수 세기

• 문제
• 답안 제출
• 통계

문제 정보

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

문제

9
5 7
1 3 2
3 5 5 6

위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다.

이 때 숫자의 합이 가장 큰 경로는 하나가 아니라 여러 개일 수 있습니다. 예를 들어 위 삼각형에서는 {9, 7, 2, 6}과 {9, 7, 3, 5}의 합이 모두 최대인 24이고, {9, 7, 3, 5}는 두 번 등장하거든요.

삼각형이 주어질 때 최대 경로의 수를 세는 프로그램을 작성하세요.

입력

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

출력

각 테스트 케이스마다 한 줄에 최대 경로의 수를 출력합니다. 
경로의 수는 230 이하라고 가정해도 좋습니다.

예제 입력

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

예제 출력

8
3

어떻게 풀까?

이번에는 경로의 개수를 세는 문제입니다.

이전 문제와 비슷하기 때문에, 이전 문제와 비슷한 코드를 이용해서 문제를 풀면 됩니다.

하지만, 경로의 수를 세야하기 때문에 이를 저장하기 위한 메모리 공간을 하나 더 만들어서 이를 처리하는 알고리즘을 또한 생성합시다!

그렇다면, 어떻게 해서 경로의 수를 저장할 수 있을까요?

경로의 수가 최신화 되는 경우를 생각해보면 됩니다.

그림을 통해 확인해 보겠습니다.

우선 위의 경우를 보면, 삼각형(1,0) 로 가는 경우의 수가 한가지이고, 삼각형 (2,0), 삼각형(2,1)에 저장된 총 합의 값이 둘 다 작으므로,

삼각형(2,0)과 삼각형(2,1)에 저장되는 경로의 수는 각각 삼각형(1,0)에 저장된 경우의 수인 1이 들어갑니다.

이 경우에는 어떻게 될까요?

들어가려는 합이 더 크기 때문에 이전에 있던 경로의 개수는 무시되고, 삼각형(1,1)로 갈 수 있는 경로 개수인 1이 들어갑니다.

그리고 위 그림과 같이 삼각형(2,2)에서 삼각형(3,2)까지의 경로의 합이 현재 삼각형(3,2)에 있는 합보다 작기 때문에 무시됩니다.

위의 경우에는 없지만, 만약에 합값이 같아지면 어떻게  해야할까요?

그렇다면, 현재 위치에서 다음 위치로 가는 경로의 수도 유효하다는 것이므로,

경로의 수를 더해주면 됩니다!

위 식을 코드로 표현하면 다음과 같습니다.

				int value1 = memoi[i][j] + triangle[i + 1][j], value2 = memoi[i][j] + triangle[i + 1][j + 1];
				if (value1 > memoi[i + 1][j])
				{
					memoi[i + 1][j] = value1;
					num[i + 1][j] = num[i][j];
				}
				else if (value1 == memoi[i + 1][j])
				{
					num[i + 1][j] += num[i][j];
				}
				if (value2 > memoi[i + 1][j + 1])
				{
					memoi[i + 1][j + 1] = value2;
					num[i + 1][j + 1] = num[i][j];
				}
				else if (value2 == memoi[i + 1][j + 1])
				{
					num[i + 1][j + 1] += num[i][j];
				}



이를 이용하여 전체 코드를 보겠습니다!

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