Close
Close full mode
logo만렙 개발자 키우기

오르막

Git RepositoryEdit on Github
Last update: a year ago by nowwaterReading time: 2 min

문제

코드

코드 보기
import java.io.*;
import java.util.*;
class Main {
static final int INF = 987654321;
static int n, arr[][], cache[][];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
cache = new int[n][n];
for(int i=0; i<n; ++i){
Arrays.fill(cache[i], -1);
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; ++j){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(solution(0, 0));
}
static int solution(int x, int y){
if(x >= n || y >= n) return INF;
if(x == n-1 && y == n-1) return 0;
if(cache[x][y] > 0) return cache[x][y];
int right = INF, down = INF, ret_right = 0, ret_down = 0;
if(y + 1 < n) right = arr[x][y+1] - arr[x][y] > 0 ? arr[x][y+1] - arr[x][y] : 0;
if(x + 1 < n) down = arr[x+1][y] - arr[x][y] > 0 ? arr[x+1][y] - arr[x][y] : 0;
ret_right = right + solution(x, y + 1);
ret_down = down + solution(x + 1, y);
return cache[x][y] = Math.min(ret_right, ret_down);
}
}

⭐️느낀점⭐️

비슷한 유형의 DP 문제를 여러번 풀어봤어서 어렵지 않게 구현할 수 있었다.

풀이 📣


1️⃣ 이동할 수 있는 방향(오른쪽, 아래쪽) 으로 움직일 수 있는지 확인한다.

2️이동이 가능하다면 오르막 점수를 획득할 수 있는지 확인한다. 현재 값보다 큰 경우에 오르막 점수 획득 가능.

3️⃣ 2차원 캐시 배열에 오른쪽과 아래쪽으로 움직였을 때의 오르막 점수의 최소값을 저장해두고, 다음에 해당 칸에 왔을 때는 이 값을 활용하여 중복 계산을 피한다.

4️⃣ (n-1, n-1) 좌표에 도달할 때 까지 위의 과정을 반복하여 최종적으로 최소 오르막 점수를 구해 출력한다.


👩‍💻 Problem Solving — Previous
알록달록한 마을 만들기
Next — 👩‍💻 Problem Solving
청백전