[JAVA] 14430번 - 자원캐기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

일단 DFS/BFS문제는 아니다. 

현재 위치에서 얻을 수 있는 최대자원을 누적해서 계산한다.

그래서 경로의 수가 아닌 각 경로에서 얻을 수 있는 자원의 최대 수를 구해야하기때문에 DP로 풀어야한다.

 

 

로봇이 탐사할 수 있는 최대 자원의 수를 구하는게 핵심이다

이전에 방문한 위치들 중 오른쪽 or 아래쪽 경로에서 올 수 있는 가장 큰 값을 누적시켜야한다

그러면 탐사할 수 있는 모든 가능한 경로 중 가장 많은 자원을 수집할 수 있는 경로를 찾아 최대 자원을 얻을 수 있다!

 

 

그럼 하나의 칸을 기준으로 생각했을때, 위에서 내려오거나, 왼쪽에서 오게된다 

그중 최댓값을 선택해서 더해가면된다.

이걸 일반화하면 이런 점화식이 된다. 그리고 뒤에 arr[i][j]를 더해주는건 자신의 값을 더해줘야하기 때문

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + arr[i][j]

 

 

시간복잡도

이차원배열이기때문에 for문을 두번 돌려야한다.

O(N*M)이다. N,M은 최대 300이라서 O(90,000) 으로 시간내에 충분히 가능하다 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 입력을 받아 이차원 배열을 만든다

2. 탐사할 수 있는 모든 경로를 탐사하면서 최대 자원을 얻는다.

3. 출력

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

1로 시작하는 배열 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] dp = new int[n+1][m+1];
        int[][] arr = new int[n+1][m+1];
        
        for(int i=1; i<=n; i++) {   
        	st = new StringTokenizer(br.readLine());
        	for(int j=1; j<=m; j++) {
        		arr[i][j] = Integer.parseInt(st.nextToken());
        	}     	   	 
        }
        
       
        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]) + arr[i][j];
        		
        	}
        }
        System.out.println(dp[n][m]);

        
    }	
}

 

0으로 시작하는 배열

=> 문제에서는 1,1이 시작이었지만 배열은 0부터 시작이니까 이렇게도 풀 수 있다.

다만 최대자원의 수를 구할때 i-1이나 j-1에서 -1이 되어서 인덱스 범위를 초과할 수 있다.

그래서 미리 첫번째 행과 첫번째 열을 채운다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] dp = new int[n][m];
        int[][] arr = new int[n][m];
        
        for(int i=0; i<n; i++) {   
        	st = new StringTokenizer(br.readLine());
        	for(int j=0; j<m; j++) {
        		arr[i][j] = Integer.parseInt(st.nextToken());
        	}     	   	 
        }
        
        dp[0][0] = arr[0][0];
        
        //첫번째 열 채우기 밑으로 이동
        for(int i=1; i<n; i++) {
        	dp[i][0] = dp[i-1][0] + arr[i][0];
        }
        
        //첫번째 행 채우기 오른쪽 이동
        for(int j=1; j<m; j++) {
        	dp[0][j] = dp[0][j-1] + arr[0][j]; 
        }
        
        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]) + arr[i][j];
        		
        	}
        }
        System.out.println(dp[n-1][m-1]);

        
    }	
}