BOJ 11048 : 이동하기

문제

---

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (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개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

 

 

출력

---

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

 

 

틀리기 쉬운 점

---

 

1. 배열을 전역변수로 선언하자.

초기화가 필요한 경우가 많은 dp 문제의 경우 자주 사용하는 방법이다.

전역변수로 선언하면 자동으로 모든 값이 0으로 초기화 된다.

'-1' 로 초기화가 하고 싶은 경우는 memset() 함수를 사용하자.

왜 '-1' 만 사용하는지는 밑에 링크에서 배우자.

 

 

2. 백준저지에선 C++ 환경에서 minmax.h 가 지원이 안된다.

귀찮지만 3개의 인수를 사용하는 경우 max 함수를 만들어서 풀도록 하자.

 

2019/08/28 - [프로그래밍/C++] - [C/C++] memset 함수 기본 사용법 및 예제

[C/C++] memset 함수 기본 사용법 및 예제

 

코드

---

#include <iostream>
#include <algorithm>
#define MAX 1000
using namespace std;

int d[MAX + 5][MAX + 5];
int arr[MAX + 5][MAX + 5];
//전역변수는 자동으로 0 초기화
//시작을 1부터 하기때문에 배열에 여유공간을 주자.

int max3(int x, int y, int z) {
	return max(x, max(y, z));
}
//백준에선 minmax.h 를 지원하지 않는다.
//귀찮지만 3개의 인수를 받는 max3 함수를 만들자.

int main() {
	int n, m;
	cin >> n >> m;

	//(1,1) 부터 입력
	for (int i = 1; i < n+1; i++) 
		for (int j = 1; j < m+1; j++) 
			cin >> arr[i][j];		
	
	for (int i = 1; i < n + 1; i++) 
		for (int j = 1; j < m + 1; j++) 
			d[i][j] = max3(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + arr[i][j];
		
	
	cout << d[n][m] << '\n';
	return 0;
}

 

코드

---

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
				
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] arr = new int[n+1][m+1];
		int[][] d = new int[n+1][m+1];
		
		
		for(int i=1; i<=n; i++) 
			for(int j=1; j<=m; j++)
				arr[i][j] = sc.nextInt();
		
		for(int i=1; i<=n; i++) 
			for(int j=1; j<=m; j++)
				 d[i][j] = Math.max(Math.max(d[i-1][j], d[i-1][j-1]) ,d[i][j-1])
				 +arr[i][j];
		
		System.out.println(d[n][m]);
						
	}
}