개발일지/Algorithm
백준 - 1937 욕심쟁이 판다 [DP]
E-room
2023. 10. 16. 14:10
728x90
1937번: 욕심쟁이 판다
n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에
www.acmicpc.net
1. 문제 요약
N * N 의 대나무 숲이 주어지고, 해당 숲에는 대나무의 양이 적혀있다.
판다는 현재 위치에서 상, 하, 좌, 우 한 곳으로 이동할 수 있으며, 이동한 곳의 대나무 양은 이전 위치보다 많아야 한다.
판다가 가장 많이 이동할 수 있는 횟수는 몇번인가?
2. 접근 방법
- 모든 대나무 숲을 방문합니다.
- 재귀 함수로 구현합니다.
# 재귀함수로 구현
def solution(y, x):
move = 0
for dy, dx in [[y-1, x], [y+1, x], [y, x-1], [y, x+1]]:
if 0 <= dy < N and 0 <= dx < N: # 이동할 좌표 범위 제한
if forest[y][x] < forest[dy][dx]: # 이동할 좌표 선정
move = max(move, solution(dy, dx) + 1)
return move
answer = 0
# 모든 칸을 방문
for y in range(N):
for x in range(N):
answer = max(answer, solution(y, x))
print(answer + 1)
- DP 방식으로 변경합니다.
3. 파이썬
dp = [[0] * N for _ in range(N)]
def solution(y, x):
if dp[y][x] != 0:
return dp[y][x]
for dy, dx in [[y-1, x], [y+1, x], [y, x-1], [y, x+1]]: #상, 하, 좌, 우
if 0 <= dy < N and 0 <= dx < N: # 이동할 좌표 범위 제한
if forest[y][x] < forest[dy][dx]: # 이동할 좌표 선정
dp[y][x] = max(dp[y][x], solution(dy, dx) + 1)
return dp[y][x]
for y in range(N):
for x in range(N):
solution(y, x)
print(max(map(max, dp)) + 1)
4. 자바
static int N;
static int[][] forest;
static int[][] dp;
static int answer = 0;
static private int solution(int y, int x) {
if (dp[y][x] != 0) {
return dp[y][x];
}
// 상, 하, 좌, 우
for (int[] temp : new int[][]{{y - 1, x}, {y + 1, x}, {y, x - 1}, {y, x + 1}}) {
int dy = temp[0];
int dx = temp[1];
// 범위 제한
if (0 <= dy && dy < N && 0 <= dx && dx < N) {
// 대나무 양 검사
if (forest[y][x] < forest[dy][dx]) {
dp[y][x] = Math.max(dp[y][x], solution(dy, dx) + 1);
}
}
}
return dp[y][x];
}
System.out.println(answer + 1);
5. 전체 코드
728x90