[백준] 11048번 이동하기 JAVA (자바) 풀이

문제 11048번 (DP)

 :  N×M 크기의 미로

    1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다

    현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다

    (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동 가능, 각 방의 사탕 획득 가능

    (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값

 

 

[입력]

 :  첫째 줄에 미로의 크기 N, M (1 ≤ N, M ≤ 1,000)

    둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며 각각의 사탕의 개수 ( 0 ≤ 사탕 ≤ 100 )

 

 

[출력]

 

 :  가져올 수 있는 사탕 개수를 출력

 

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

1. (r+1, c), (r, c+1), (r+1, c+1) 이용하기

• 아래로 한 칸 / 우로 한 칸 / 대각선으로 한 칸 이동이 가능하다
  
  
• dp는 이전지점의 값들을 불러오기 위함이다 
  
  • 이말은 즉 아래로 한 칸 오기전, 우로 한 칸 오기전의 dp값이 필요
  • dp[i-1][j] / dp[i][j-1] / dp[i-1][j-1] 에서 가장 최대인 값을 고르고
  • arr[i][j] 현지점의 사탕개수를 추가해서 현 지점의 dp[i][j]를 만든다
  • dp[i] 로 시작지점고정
    모든 시작지점은 카운트 1값을 가진다
    현지점에서 수열을 세기 시작한다면 1이기 때문이다
    

 

 

 [코드]

import java.io.*;
import java.util.*;
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(Math.max(dp[i-1][j],dp[i][j-1]),+dp[i-1][j-1])+arr[i][j];
            }
        }
        System.out.println(dp[N][M]);
    }
}

 

 

 [해설]
     

 :  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];  dp 배열
    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++){ 아래로 이동전 / 우로 이동전 / 대각선 이동전 dp중 최대값 찾기
            for(int j=1; j<=M; j++){  최대값 찾았으면 현재 지점 사탕개수 더해주기
                dp[i][j] = Math.max(Math.max(dp[i-1][j],dp[i][j-1]),+dp[i-1][j-1])+arr[i][j];
            }
     }

 :  System.out.println(dp[N][M]);  결과 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

https://www.acmicpc.net/problem/11048

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *