[백준 2157] 여행

문제 출처

1. 구상

• 출발지, 도착지, 점수를 저장하는 배열 만들기

• 출발지 → 도착지의 점수의 최대값을 저장하는 배열 만들기

• 입력하는 점수 값과 전 최대값 + 점수값을 비교하여 최대 값을 저장
  → 메모리 초과 오류 발생

• 도시 번호와 이동 횟수를 이용하여 다음 도시로 이동하였을 때 최대 값과 (현재 위치의 최대값 + 현재 도시 → 다음 도시의 점수 값)을 비교하여 큰 값을 저장

2. 1번째 구현 (메모리 초과)

import java.util.*;
import java.io.*;

public  class Main {	
	
	public static int[][] dp;
	public static int[][] arr;
	public static int sta = 0;
	public static int fin = 0;	
	public static int cas = 0;
	
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(System.in);
		
		sta = s.nextInt();
		fin = s.nextInt();
		cas = s.nextInt();
		
		dp = new int[cas+1][cas+1];		
		arr = new int[cas][3];
		
		for (int i = 0; i < cas; i++) {
			arr[i][0] = s.nextInt();
			arr[i][1] = s.nextInt();
			arr[i][2] = s.nextInt();
		}
		
		for (int i = 0; i < cas; i++) {
			lis(arr[i][0], arr[i][1], arr[i][2]);
		}
		int max = dp[0][3];
		
		for (int i = 1; i < cas + 1; i++) {
			if (max < dp[i][3])
				max = dp[i][3];
		}
			
		
		System.out.print(max);
				
	}
	
	
	
	public static int lis(int i, int k, int val) {
		if(i <= 0)
			return 0;
		
		if (dp[i][k] == 0)
			dp[i][k] = val;
		
		else 
			dp[i][k] = Math.max(dp[i][k], dp[k][3] + val);
			
			
		
		return dp[i][k];
	}
	
} 

3. 2번째 구현

import java.util.*;
import java.io.*;

public  class Main {	
	
    //점수 최대값을 저장하는 배열
	public static int[][] dp;	
    //출발지, 도착지, 점수를 저장하는 배열
	public static int[][] edge;
	public static int m;
    //유효하지 않은 값을 나타내는 상수
	public static final int INVALID = -1;
	
	
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt();
		m = s.nextInt();
		int k = s.nextInt();
		
        //(도시 개수 + 1) * (거치는 도시 개수 + 1)만큼
		dp = new int[n+1][m+1];		
        //(도시 개수 + 1) * (도시 개수 + 1)만큼
		edge = new int[n+1][n+1];
		
        //배열 초기화
		for (int[] row : edge) Arrays.fill(row, INVALID);
		
		for (int i = 0; i < k; i++) {
			int a = s.nextInt();
			int b = s.nextInt();
			int c = s.nextInt();
			
            //출발지보다 도착지의 번호가 크다면 배열에 저장X
			if(a > b)
				continue;
			
            //같은 경로라면 점수가 높은 것만 저장
			edge[a][b] = Math.max(edge[a][b], c);
		}
		
        //배열 초기화
		for (int[] row : dp) Arrays.fill(row, INVALID);
        
        //시작 도시의 점수 값은 0으로 
        dp[1][1] = 0;
        for (int curCity = 1; curCity < n; curCity++) {
            for (int arrivedCnt = 1; arrivedCnt < m; arrivedCnt++) {
            	//현재 도시 위치의 점수 최대값이 없다면 넘어가기
                if (dp[curCity][arrivedCnt] == INVALID) continue;

                for (int nextCity = curCity+1; nextCity <= n; nextCity++) {
                	//현재 도시 위치의 점수값이 없다면 넘어가기
                    if (edge[curCity][nextCity] == INVALID) continue;
                    
                    /*다음 도시의 점수 최대값은 다음 도시의 최대값과 
                    현재 도시의 최대값 + 해당 경로의 점수를 비교*/
                    dp[nextCity][arrivedCnt+1] = Math.max(dp[nextCity][arrivedCnt+1], dp[curCity][arrivedCnt] + edge[curCity][nextCity]);
                }
            }
        }

  //dp 배열 중 최대값을 출력
  System.out.println(Arrays.stream(dp[n]).max().getAsInt());
		
				
	}
	
	
	
	
	
} 

코드 및 알고리즘 참고 링크