[BOJ 1520번] 내리막길(JAVA)

www.acmicpc.net/problem/1520

1520번: 내리막 길

import java.io.*;
import java.util.*;

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   static StringBuilder sb=new StringBuilder();
   static int[][] arr, answer;
   static int M, N;
   
   public static void main(String args[]) throws Exception {
	   String str[]=br.readLine().split(" ");
	   M=Integer.parseInt(str[0]);
	   N=Integer.parseInt(str[1]);
	   arr=new int[M][N];
	   answer=new int[M][N];
	   for(int i=0;i<M;i++) {
		   String str2[]=br.readLine().split(" ");
		   for(int j=0;j<N;j++) {
			   arr[i][j]=Integer.parseInt(str2[j]);
			   answer[i][j]=-1;
		   }
	   }
	   System.out.println(function(0, 0));
   }
   
   public static int function(int ii, int jj) {
	   if(ii==M-1&&jj==N-1) {
		   return 1;
	   }
	   if(answer[ii][jj]==-1) {
		   answer[ii][jj]=0;
		   if(ii>0 && arr[ii][jj]>arr[ii-1][jj]) {
			   answer[ii][jj]+=function(ii-1, jj);
		   }
		   if(jj>0&&arr[ii][jj]>arr[ii][jj-1]) {
			   answer[ii][jj]+=function(ii, jj-1);
		   }
		   if(ii<M-1&&arr[ii][jj]>arr[ii+1][jj]) {
			   answer[ii][jj]+=function(ii+1, jj);
		   }
		   if(jj<N-1&&arr[ii][jj]>arr[ii][jj+1]) {
			   answer[ii][jj]+=function(ii, jj+1);
		   }
	   }
	   return answer[ii][jj];
   }
}

 이 문제에 대해 찾아보던 중 메모이제이션(memoization)이란 개념에 대해 알게 되었습니다.

메모이제이션이란 반복 계산을 할 때 이전에 계산한 값을 메모리에 저장해 계산 과정이 겹치는 것을 방지하는 기술입니다.

자세한 내용은 아래 링크를 첨부해 놓겠습니다.

ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

메모이제이션 - 위키백과, 우리 모두의 백과사전

그래서 처음에 메모이제이션을 적용하지 않고 재귀를 이용해서 문제를 풀었습니다.

import java.io.*;
import java.util.*;

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   static StringBuilder sb=new StringBuilder();
   static int[][] arr;
   static int answer=0, M, N;
   
   public static void main(String args[]) throws Exception {
	   String str[]=br.readLine().split(" ");
	   M=Integer.parseInt(str[0]);
	   N=Integer.parseInt(str[1]);
	   arr=new int[M][N];
	   for(int i=0;i<M;i++) {
		   String str2[]=br.readLine().split(" ");
		   for(int j=0;j<N;j++) {
			   arr[i][j]=Integer.parseInt(str2[j]);
		   }
	   }
	   function(0, 0);
	   System.out.println(answer);
   }
   
   public static void function(int ii, int jj) {
	   if(ii==M-1&&jj==N-1) {
		   answer++;
		   return;
	   }
	   if(ii+1<=M-1) {
		   if(arr[ii+1][jj]<arr[ii][jj]) function(ii+1, jj);
	   }
	   if(jj+1<=N-1) {
		   if(arr[ii][jj+1]<arr[ii][jj]) function(ii, jj+1);
	   }
	   if(ii-1>=0) {
		   if(arr[ii-1][jj]<arr[ii][jj]) function(ii-1, jj);
	   }
	   if(jj-1>=0) {
		   if(arr[ii][jj-1]<arr[ii][jj]) function(ii, jj-1);
	   }
   }
}

 테스트케이스는 잘 돌아갔지만, 시간 초과 문제에 걸리게 되었는데요, 메모이제이션을 적용해 위의 코드처럼 작성하니 문제를 해결할 수 있었습니다.