반응형
https://www.acmicpc.net/problem/1937
1937번: 욕심쟁이 판다
n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에
www.acmicpc.net
[ 문제풀이 ]
1. 대나무 숲을 저장할 arr 배열과, 메모이제이션을 위한 dp 배열을 만듭니다.
2. dp[ i ][ j ]에는 i, j 좌표에서 시작했을 때 가장 많이 이동할 수 있는 칸의 수를 저장합니다.
3. 따라서, 한번 저장한 좌표에는 다시 갈 필요가 없으므로 dp[ i ][ j ] != 0일 때 dp[ i ][ j ]를 return 합니다.
4. 그렇지 않다면 arr[ yy ][ xx ] > arr[ y ][ x ] 일 때, dp[ y ][ x ] = max(dp[ y ][ x ], dfs(yy, xx) + 1)의 점화식을 이용하여 각 좌표의 최댓값을 저장해 줍니다.
5. 모든 좌표를 2중 for문을 이용해 돌며 dfs를 실행하고, 그중 최댓값을 ans에 저장합니다.
6. ans를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include<iostream> using namespace std; int n; int arr[500][500]; int dp[500][500]; int dy[4] = { -1,1,0,0 }; int dx[4] = { 0,0,-1,1 }; int ans; int dfs(int y, int x) { int& ret = dp[y][x]; if (ret != 0) return ret; ret = 1; for (int i = 0; i < 4; i++) { int yy = y + dy[i]; int xx = x + dx[i]; if (yy >= 0 && yy < n && xx >= 0 && xx < n) { if (arr[yy][xx] > arr[y][x]) { ret = max(ret, dfs(yy, xx) + 1); } } } return ret; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &arr[i][j]); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans = max(ans,dfs(i, j)); } } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1944번 - 복제 로봇 (C++) (0) | 2023.02.17 |
|---|---|
| [ 백준 ] 14621번 - 나만 안되는 연애 (C++) (0) | 2023.02.16 |
| [ 백준 ] 7570번 - 줄 세우기 (C++) (0) | 2023.02.14 |
| [ 백준 ] 11085번 - 군사 이동 (C++) (0) | 2023.02.13 |
| [ 백준 ] 2565번 - 전깃줄 (C++) (0) | 2023.02.12 |