어흥
[백준 1937] 욕심쟁이 판다 (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/1937
1. 주의할 점
- 메모아이징 기법을 이용한다
- 값을 저장해서 사용하는 형태로 한다
2. 구현
- 모든 수를 입력 받고, Check[][] 배열에는 현재 지점에서 시작하여 살 수 있는 최대 일수를 저장한다
- 만약 Check[][] 값이 0이라면 DFS()를 수행한다
- DFS(y,x) 함수에는 이미 해당 Check[y][x] 값이 양수라면 해당 값을 반환한다. 0이라면, 현재 위치를 기준으로 4방 탐색을 통해 대나무가 더 많은 쪽으로 이동하여 값을 갱신할 수 있도록 한다
- Int 반환형을 통해 이동했던 쪽으로 갈 수 있는 최대값을 계속해서 Return 받으며, Return 받은 최대값+1을 현재 위치의 Check[][] 배열에 저장한다
- Check[][] 배열중에서 가장 큰 값을 출력한다
#include <iostream>
#include <algorithm>
using namespace std;
int arr[500][500], check[500][500], num;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int dfs(int y, int x) {
int &ret = check[y][x];
if (check[y][x]) return ret;
int temp = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < num && ny<num && arr[ny][nx]>arr[y][x]) {
temp = max(temp, dfs(ny, nx));
}
}
ret = temp + 1;
return ret;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> num;
for (int i = 0; i < num; i++)
for (int j = 0; j < num; j++)
cin >> arr[i][j];
int result = 0;
for (int i = 0; i < num; i++)
for (int j = 0; j < num; j++)
if (check[i][j] == 0)
dfs(i, j);
for (int i = 0; i < num; i++)
for (int j = 0; j < num; j++)
result = max(result, check[i][j]);
cout << result;
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 9944] NxM 보드 완주하기 (C++) (0) | 2020.12.03 |
---|---|
[백준 12781] PIZZA ALVOLOC (C++) (0) | 2020.11.29 |
[백준 14725] 개미굴 (C++) (0) | 2020.11.05 |
[백준 13911] 집 구하기 (C++) (0) | 2020.10.29 |
[백준 1092] 배 (C++) (4) | 2020.10.26 |
Comments