백준 4811 <알약>

오랜만에 DP문제를 풀어보았다.

 

딱 봐도 총길이가 2N이면 30개를 한다고 치면 3814986502092304번... 당연히 시간 초과가 나는 문제 

 

이런 문제는 일반적으로 DP라고 보면된다.

 

이 문제의 dp는 언제가 끝나는 조건인가? 당연히 한 조각 전체 알약이 없거나 한 조각이 하나와 반 조각이 없을 경우이다!

 

그리고 차곡차곡 dp에 값을 저장해서 값이 있다면 그 값을 return~하는 그런 문제이다!

 

문제 풀이

1. dp [][] 배열을 생성하고 현재 find 함수에 (알약-1,1) <<이유는 시작은 어차피 한 개 알약이기 때문
2. 한 조각 전체 알약이 없을 경우나 한조 강 알약이 하나 남고 반 조각이 없으면 시도할 경우가 1가지 밖에 없기 때문에 1 return!!   
3. dp에 값이 저장되어있으면 이 값을 return 하고 아니면 계속 find 함수 호출

주의사항!! 알약 반개의 개수가 음수가 되면 0 리턴해주기!!

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{

	static long map[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		map=new long[31][31];

		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		while(n!=0) {
			System.out.println(find(n-1,1));
			n=Integer.parseInt(br.readLine());
		}
	}
	private static long find(int i, int j) {
		// TODO Auto-generated method stub
		if(i==0||i==1&&j==0)
			return 1;
		if(j<0) {
			return 0;
		}
		if(map[i][j]!=0) {
			return map[i][j];
		}
		map[i][j]=0;
		map[i][j]+=find(i-1,j+1)+find(i,j-1);
		return map[i][j];
	}

}