프로그래머스 서울에서 경산까지(java)

https://programmers.co.kr/learn/courses/30/lessons/42899
주어진 시간안에 최대의 모금액을 모을 수 있는 경우를 찾아야하는 문제이다. 각각의 이동에서는 자전거와 도보로 갈 수 있는 두가지 방법이있다.

상세 풀이

 int[][] dp=new int[travel.length][K+1];
        dp[0][travel[0][0]]=travel[0][1];
        dp[0][travel[0][2]]=travel[0][3];

dp라는 배열을 선언하여 도시에 해당시간까지 모은 최대 모금액을 저장한다.비교를 위해 dp에 도보로 걸린 시간인 travel[0][0]위치에 모금액인 travel[0][1]를 넣는다. 자전거의 경우도 마찬가지로 넣어준다.

 for(int i=1;i<travel.length;i++){
        	for(int k=0;k<=K;k++){
        		if(dp[i-1][k]==0){
        			continue;
        		}
        		if(travel[i][0]+k<=K){
        			dp[i][k+travel[i][0]]=Math.max(dp[i][k+travel[i][0]], dp[i-1][k]+travel[i][1]);
        			answer=Math.max(answer,dp[i][k+travel[i][0]] );
        		}
        		if(travel[i][2]+k<=K){
        			dp[i][k+travel[i][2]]=Math.max(dp[i][k+travel[i][2]], dp[i-1][k]+travel[i][3]);
        		answer=Math.max(answer,dp[i][k+travel[i][2]] );
        		}

        	}

도시 전체를 K시간을 소모하여야하기때문에 이중 for문을 사용한다. 다음 도시까지 두가지중 선택하기 위해 해당 루트를 선택하였을 때 주어진 시간을 초과하지 않는 것을 조건으로 한다. 그리고 전 도시까지의 최대값에 해당 루트의 모금액과 더해준 값과 기존의 해당 시간 값을 비교하여 더 큰 모금액을 저장한다. return값인 answer역시 비교해준다.이렇게 for문이 모두 완료되면 answer에는 해당 시간동안 모을 수 있는 최대값이 된다.

코드

public int solution(int K, int[][] travel) {
        int answer = 0;
        int[][] dp=new int[travel.length][K+1];
        dp[0][travel[0][0]]=travel[0][1];
        dp[0][travel[0][2]]=travel[0][3];
        for(int i=1;i<travel.length;i++){
        	for(int k=0;k<=K;k++){
        		if(dp[i-1][k]==0){
        			continue;
        		}
        		if(travel[i][0]+k<=K){
        			dp[i][k+travel[i][0]]=Math.max(dp[i][k+travel[i][0]], dp[i-1][k]+travel[i][1]);
        			answer=Math.max(answer,dp[i][k+travel[i][0]] );
        		}
        		if(travel[i][2]+k<=K){
        			dp[i][k+travel[i][2]]=Math.max(dp[i][k+travel[i][2]], dp[i-1][k]+travel[i][3]);
        		answer=Math.max(answer,dp[i][k+travel[i][2]] );
        		}

        	}
        }


        return answer;
    }