최대 평균값이있는 경로

난이도 쉽게
자주 묻는 질문 시스코 에픽 시스템 그레이 오렌지 SAP 연구소 타임즈 인터넷
배열 동적 프로그래밍 매트릭스조회수 28
링크드 인버퍼레딧텀블러

문제 정책

"최대 평균값이있는 경로"문제는 2D 배열 또는 정수 행렬이 제공된다는 것을 나타냅니다. 이제 왼쪽 상단 셀에 서 있고 오른쪽 하단에 도달해야한다고 가정합니다. 목적지에 도달하려면 하단 방향 또는 올바른 방향으로 이동해야합니다. 목적지 별, 여기서는 오른쪽 하단 셀을 의미합니다. 한 가지 조건은 최대 평균 값을 제공하는 경로를 따라 이동해야한다는 것입니다.

예

3 3 // number of rows and columns
1 1 2
10 1 100
10 10 1
22.6

설명

최대 평균값이있는 경로핀

다음과 같은 방식으로 왼쪽 상단 셀에서 이동했습니다. 1-> 10-> 1-> 100-> 1.이 값을 더하면 총합이 113이됩니다. 따라서 평균은 113/5 = 22.6이됩니다.

접근

무차별 대입 접근 방식을 생각해 낼 수 있는데, 이는 오른쪽 하단 셀에 도달 할 수있는 모든 방법을 생성하는 것입니다. 일단 모든 경로를 생성했습니다. 이제 그것들로 이동하여 경로에있는 정수의 합을 찾으십시오. 그래서, 일단 당신이 모든 합계를 가지면. 이들 중 최대 값을 구하십시오.

그러나이 접근 방식을 사용하면 TLE로 이동하거나 시간 제한을 초과하게됩니다. 그러한 경로의 생성은 기하 급수적 인 시간 복잡성으로 이어질 것이기 때문입니다. 따라서 시간 제약 하에서 문제를 해결합니다. 효율적인 솔루션을 찾아야합니다. 하지만 어떻게 할 수 있습니까? 동적 프로그래밍을 사용하여이를 수행 할 수 있습니다. 또한 문제는 Maximum Path Sum 문제와 매우 유사합니다. 이 문제에서 우리는 2D 배열에서 최대 경로 합을 찾아야합니다. 우리가 할 일도 똑같지 만 결국에는 평균을 낼 것입니다.

그래서 동적 프로그래밍 접근하다. DP 매트릭스의 각 셀이 왼쪽 상단 모서리에서 현재 셀로 시작해야하는 경우 얻을 수있는 최대 합계를 나타내는 2D DP 배열을 만듭니다. 그래서 우리는 일반적인 반복 관계를 작성할 수 있습니다.

// 기본 케이스
dp [0] [0] = a [0] [0]
dp [i] [0] = dp [i-1] [0] + a [i] [0] // 여기서 i는 첫 번째 행부터 행렬의 마지막 행까지 시작합니다.
dp [0] [i] = dp [0] [i-1] + a [0] [i] // 여기서 i는 첫 번째 열부터 행렬의 마지막 열까지 시작합니다.
// 반복 관계
dp [i] [j] = max (dp [i-1] [j], dp [i] [j-1]) + a [i] [j] // 다른 모든 셀

평균값이 최대 인 Path에 대한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  int n,m; // number of rows and columns in input matrix
  cin>>n>>m;

  int input[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++)
      cin>>input[i][j];
  }

  int dp[n][m];
  dp[0][0] = input[0][0];
  for(int i=1;i<n;i++)
    dp[i][0] = dp[i-1][0] + input[i][0];
  for(int i=1;i<m;i++)
    dp[0][i] = dp[0][i-1] + input[0][i];

  for(int i=1;i<n;i++){
    for(int j=1;j<m;j++)
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + input[i][j];
  }

  // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
  cout<<(dp[n-1][m-1]/((double)n+m-1));
}

3 3
1 1 2
10 1 100
10 10 1
22.6

평균값이 최대 인 Path에 대한 Java 코드

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); int m = sc.nextInt(); // number of rows and columns in input matrix

    int input[][] = new int[n][m];
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++)
        input[i][j] = sc.nextInt();
    }

    int dp[][] = new int[n][m];
    dp[0][0] = input[0][0];
    for(int i=1;i<n;i++)
      dp[i][0] = dp[i-1][0] + input[i][0];
    for(int i=1;i<m;i++)
      dp[0][i] = dp[0][i-1] + input[0][i];

    for(int i=1;i<n;i++){
      for(int j=1;j<m;j++)
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + input[i][j];
    }

    // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
    System.out.print(dp[n-1][m-1]/((double)n+m-1));
  }
}
3 3
1 1 2
10 1 100
10 10 1
22.6

복잡성 분석

시간 복잡성

O (N ^ 2) 단순히 입력 배열을 순회했기 때문입니다. 그리고 DP의 전환은 O (1) 시간 밖에 걸리지 않았습니다.

공간 복잡성

O (N ^ 2) 2D DP 어레이를 만들었 기 때문입니다.

링크드 인버퍼레딧텀블러
Translate »