BOJ - 1937 욕심쟁이 판다
1937번 욕심쟁이 판다
판다가 현재 위치하고 있는 곳의 대나무를 다 먹고 상하좌우로 이동을 한다. 이 때 이동할 곳의 대나무가 현재 있던 곳의 대나무보다 적다면 이동을 하지 않고 굶어 죽는다.
위의 상황에서 판다를 어딘가에 처음 위치 시켰을 때 판다가 가장 오래 살아있을 수 있는 기간을 구하는 문제이다.
문제 해결 전략
예를 들어 판다가 (1,1)->(1,2)->(2,2)로 이동을 했다고 생각해 보자.
(1,1)에서 출발 했을 때의 살아있는 기간은 3일이 된댜.
그리고 (1,2)에서 출발했을 때의 살아있는 기간은 2일이 된다.
만약 이전에 선택한 좌표에서의 이동 경로 중 현재 선택한 좌표가 있다면 현재 선택한 좌표는 무조건 이전 좌표의 날 수 보다 작을 것이니 따로 계산을 할 필요가 없다.
또한 새로 선택한 좌표에서 출발하는 경우 이동 경로 중 다른 좌표에서 출발할 때 거쳤던 곳을 한번 더 거친다면 그 때 저장된 값과 현재 누적된 값을 비교하여 더 큰 값을 저장해 준다.
즉, DP를 활용하여 저장된 값을 활용하는 것이다.
문제 해결 순서는 다음과 같다.
-
대나무의 양을 내림차순으로 정렬한다.
-
대나무의 양이 많은 곳부터 적은 곳으로 이동을 한다.
-
이동 과정에서 이동할 곳에 저장되어 있는 기간 과 현재 기간 + 1 을 비교하여 더 큰 값을 저장해 준다.
-
저장된 값 중 가장 큰 값을 구한다.
코드
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int arr[501][501];
int visited[501][501];
int xpo[4] = {-1,1,0,0};
int ypo[4] = {0,0,-1,1};
vector<pair<int, pair<int,int>>> v;
int n;
int dp(){
for(int i=0;i<v.size();i++)
{
int x = v[i].second.first;
int y = v[i].second.second;
for(int j=0;j<4;j++)
{
int nx = x + xpo[j];
int ny = y + ypo[j];
if(nx < 0 || nx >= n || ny < 0 || ny >= n)
continue;
if(arr[nx][ny] > arr[x][y])
{
if(visited[x][y] < visited[nx][ny] + 1)
visited[x][y] = visited[nx][ny] + 1;
}
}
if(visited[x][y] == 0)
visited[x][y] = 1;
}
int max = 0;
for(int k=0;k<n;k++)
{
for(int j=0;j<n;j++)
{
if(visited[k][j] > max)
max = visited[k][j];
}
}
return max;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin >> arr[i][j];
v.push_back(make_pair(-arr[i][j], make_pair(i,j)));
}
}
sort(v.begin(), v.end());
cout << dp();
return 0;
}
출처 : https://www.acmicpc.net/problem/1937
Author And Source
이 문제에 관하여(BOJ - 1937 욕심쟁이 판다), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kms9887/BOJ-1937-욕심쟁이-판다저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)