👀 문제 설명
n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다.
이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.
입력
첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.
예제 입력 1
4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8
예제 출력 1
4
✍🏻풀이
처음에는 입력받은 대나무의 양 중 가장 작은 것부터 순서대로 Dynamic Programming을 하면 된다고 생각해서, 제일 작은 값과 위치를 저장해뒀다.
이렇게 하니까 너무 복잡해지고 그 다음 작은 값은 또 어떻게 구해야할지 막막해졌다 :(
그래서 구글링을 통해.. 알아낸 방법은 다음과 같다.
상수 선언
#define MAX 500 : 대나무 숲의 크기는 최대 500
필요한 변수
int n : 입력받을 대나무 숲의 크기
int forest[MAX][MAX] : 대나무 숲의 각각 위치에 대나무 양이 얼마나 있는지를 입력받을 테이블
int dx[4] & int dy[4] : 상, 하, 좌, 우를 위한 배열
int dp[MAX][MAX] : Dynamic Programming을 위한 테이블
알고리즘
1. 대나무 숲을 입력받는다.
2. 각각의 위치에서 Dynamic Programming을 다 해본다.
-> 이 때, 메모이제이션(Memoization) 사용! (참고 : [Algorithm] Dynamic Programming)
3. 그 중 제일 큰 값이 답 (max 함수 사용)
쓰니까 너무 간단하네..
코드
//
// BOJ_1937.cpp
// Algorithm
//
// Created by 조수민 on 2020/05/17.
// Copyright © 2020 조수민. All rights reserved.
//
// 욕심쟁이 판다(https://www.acmicpc.net/problem/1937)
#include <iostream>
#include <vector>
#define MAX 500 // 대나무 숲 크기는 최대 500
//#define BAMBOO 1000000 // 대나무 양은 최대 1,000,000 (이지만, 사용하지 않는 값)
using namespace std;
int n; // 대나무 숲 크기
int forest[MAX][MAX];
int dx[4] = { -1, 1, 0, 0 }; // 상, 하, 좌, 우
int dy[4] = { 0, 0, -1, 1}; // 상, 하, 좌, 우
int dp[MAX][MAX]; // dp 저장공간..
// 대나무 숲 입력받기
void input()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
dp[i][j] = 1; // dp를 1로 초기화해둔다.
cin >> forest[i][j];
}
}
int get_day(int x, int y)
{
int &day = dp[x][y];
if (day != 1)
return day;
for (int i = 0; i < 4; i++)
{
int next_x = x + dx[i];
int next_y = y + dy[i];
// next_x와 next_y가 범위를 벗어난다면 continue문 수행
if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= n)
continue;
// 다음 위치의 대나무 양이 현재 위치의 대나무 양보다 클 떄만 다음을 수행한다.
if (forest[next_x][next_y] > forest[x][y])
{
// 메모이제이션 사용!
int next_dynamic = get_day(next_x, next_y) + 1; // 다음으로 이동해서 그 자리에서 또 get_day를 한다.
day = max(day, next_dynamic); // day와 next_dynamic 중 더 큰 값을 day에 넣어준다.
}
}
return day;
}
int get_answer()
{
int answer = 0;
// 각각의 위치에서 dynamic_programming을 다 해본다.
// 그 중 제일 큰 값이 답
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
answer = max(answer, get_day(i, j)); // 매번 answer와 (i, j) 위치에서의 dynamic_programming 값을 비교하여 더 큰 값을 answer로 바꿔준다.
return answer;
}
int main()
{
input();
cout << get_answer() << endl;
return 0;
}
'숨막히는 알고말고 > 문제 풀이' 카테고리의 다른 글
[Baekjoon] 피보나치 수의 확장(BOJ 1788) (0) | 2020.07.15 |
---|---|
[Baekjoon] 정상회담 2(BOJ 1670) (0) | 2020.07.15 |
[Baekjoon] 토너먼트(BOJ 1057) (0) | 2020.06.23 |
[Baekjoon] 약수(BOJ 1037) (2) | 2020.06.20 |
[Baekjoon] 로봇 조종하기(BOJ 2169) (2) | 2020.05.18 |