[백준] 9184 - 신나는 함수 실행 (JAVA)

1. 소요시간 : 15분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 2
4. 문제 유형 : 다이나믹 프로그래밍 , 재귀
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : O
7. 문제 링크 : https://www.acmicpc.net/problem/9184
8. 푼 날짜 : 2023.03.07

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.
사실 점화식을 유도했다기 보다는 메모이제이션만을 사용했다.

2. 풀이과정

다이나믹 프로그래밍이 부족하다고 다이나믹 프로그래밍 문제들을 계속 다시 풀어보고 있다.
문제에 적힌 거의 그대로 구현했다.
이미 한 번 구한 것을 여러 번 다시 구하는 작업이 반복되므로 메모이제이션을 사용해서
중복되는 연산을 수행하지 않도록 했다. 중복되는 연산을 수행한다면 TLE 가 날것이 분명하다.

3. 소스코드

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


public class Main{
	
	static Integer arr[][][]=new Integer[51][51][51];
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb=new StringBuilder();

		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());
			if(a==-1&&b==-1&&c==-1) break;
			
			int ans= w(a,b,c);
			sb.append("w("+a+", "+b+", "+c+") = "+ans+"\n");
			
		}
		System.out.println(sb);
		
	}
	
	public static int w(int a,int b,int c) {
		if(a<=0||b<=0||c<=0) return 1;
		
		else if(a>20||b>20||c>20) {
			if(arr[20][20][20]!=null)
				return arr[20][20][20];
			else {
				arr[20][20][20]=w(20,20,20);
				return arr[20][20][20];
			}
		}
		else if(a<b&&b<c) {
			
			if(arr[a][b][c-1]==null) {
				arr[a][b][c-1]=w(a,b,c-1);
			}
			if(arr[a][b-1][c-1]==null) {
				arr[a][b-1][c-1]=w(a,b-1,c-1);
			} 
			if(arr[a][b-1][c]==null) {
				arr[a][b-1][c]=w(a,b-1,c);
			}
			return arr[a][b][c-1] + arr[a][b-1][c-1]-arr[a][b-1][c];
			
		}
		else {
			if(arr[a-1][b][c]==null) {
				arr[a-1][b][c]=w(a-1,b,c);
			}
			if(arr[a-1][b-1][c]==null) {
				arr[a-1][b-1][c]=w(a-1,b-1,c);
			} 
			if(arr[a-1][b][c-1]==null) {
				arr[a-1][b][c-1]=w(a-1,b,c-1);
			}
			if(arr[a-1][b-1][c-1]==null) {
				arr[a-1][b-1][c-1]=w(a-1,b-1,c-1);
			}
			return arr[a-1][b][c] + arr[a-1][b-1][c]+arr[a-1][b][c-1]-arr[a-1][b-1][c-1];
		}
		
		
	}
}

4. 결과

5. 회고

다이나믹 프로그래밍을 잘해보자 !

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212