[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)9184번, 신나는 함수 실행

문제 링크

9184번: 신나는 함수 실행

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

위 문제에서는 함수 w를 재귀하여 불필요하게 반복하고 있습니다.

그래서 처음에 해당하는 연산값을 따로 메모이제이션에 저장한 뒤에 똑같은 연산을 실행하기전 저장한 연산값을 가져와서 연산을 실행하지 않고 진행하는 것입니다.

음수 값을 받으면 무조건 1이 출력되기 때문에 자연수 중 최대값인 50을 기준으로 메모이제이션 배열 크기를 51로 설정하였습니다.

 

• 함수 값 저장할 메모이제이션 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 띄어쓰기 기준으로 입력값을 a, b ,c에 저장하였습니다.
• 신나는 함수 w을 만들었습니다.

• check가 null이 아니면 메모이제이션에 저장된 값이 있기에 그 값을 가져온다.
• null인 경우 재귀를 반복하여 결과값을 메모이제이션에 저장한 뒤 반환한다.
• 문제에 있는 함수를 토대로 w을 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Integer[][][] check = new Integer[51][51][51];	//메모이제이션 배열
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	StringTokenizer st;
        //--------------입력값 받은 후 함수 실행 및 결과 출력-------------
    	while(true) {
        	//입력값 받기
    		st = new StringTokenizer(br.readLine()," ");
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		int c = Integer.parseInt(st.nextToken());
            //-1,-1,-1입력 받을시 종료
    		if(a==-1 && b==-1 && c==-1)
    			break;
            //결과 출력
    		System.out.println("w(" + a + ", " + b + ", " + c + ") = " + w(a,b,c));
    	}
    	br.close();
	}
    //-----------------------신나는 함수 실행----------------
	public static int w(int a, int b, int c) {
		if(a<=0 || b<=0 || c<=0)
			return 1;
		//메모이제이션에 값 존재시 그 값 반환
		if(check[a][b][c]!=null)
			return check[a][b][c];
		//----------메모이제이션 없을 시 값 저장 및 반환---------
		if(a>20 || b>20 || c>20) 
			check[a][b][c] = w(20,20,20);
		else if(a<b && b<c) 
			check[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);
		else 
			check[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1);
		
		return check[a][b][c];
	}
}