[BOJ] dynamic programming / 14단계

1	1003	피보나치 함수
단순 재귀로 피보나치 수를 구하면 왜 느릴까요? 함수 호출의 개수가 기하급수적으로 늘어나기 때문입니다

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bfr.readLine());
		for(int i=0; i<T; i++) {
			int num = Integer.parseInt(bfr.readLine());
			int zero = 1;
			int one = 0;
			int temp;
			for(int j=0; j<num; j++) {
				temp = one;
				one = zero + one;
				zero = temp;
			}
			System.out.println(zero + " " + one);
		}
	}

}

---

2	9184	신나는 함수 실행
재귀 호출만 생각하면 신이 난다! 아닌가요?

import java.util.Scanner;

public class Main {
	static int array[][][] = new int[51][51][51];
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a=0, b=0, c=0;
		while(true){
			a = scan.nextInt();
			b = scan.nextInt();
			c = scan.nextInt();
			if(a==-1 && b==-1 && c==-1) break;
			System.out.printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));
			
		}

	}
	
	static int w(int a, int b, int c) {
		if(a<=0 || b<=0 || c<=0)
			return 1;
		else if(array[a][b][c] != 0)
			return array[a][b][c];
		else if(a>20 || b>20 || c>20)
			return array[a][b][c] = w(20,20,20);
		else if(a<b && b<c)
			return array[a][b][c] = w(a,b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
		else
			return array[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);
	}

}

---

3	1904	01타일
점화식의 값을 특정 상수로 나눈 나머지를 구하는 문제

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

public class Main {
	static int[] array = new int [1000001];

	public static void main(String[] args) throws IOException {
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bfr.readLine());
		array[0] = 1;
		array[1] = 2;
		array[2] = 3;
		for(int i=3; i<=N; i++) {
			array[i] = array[i-1] + array[i-2];
			array[i] %= 15746;
				
		}
		System.out.println(array[N-1]);
		
	}

}

---

4	9461	파도반 수열
피보나치 수와 비슷한 규칙을 찾아 동적 계획법으로 푸는 문제

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		for(int i =0; i<T; i++) {
			int a = scan.nextInt();
			if(a==1 || a==2 || a==3) {
				System.out.println(1);
				continue;
			}
	
			Long array[] = new Long[a];
			array[0] =(long) 1;
			array[1] =(long)1;
			array[2] =(long)1;
			
			for(int j=3; j<a; j++) {
				array[j] = array[j-3] + array[j-2];
			}
			
			System.out.println(array[a-1]);
		}

	}

}

---

5	1149	RGB거리
i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의해봅시다.

import java.util.Scanner;

public class Main {
	static int T;
	static int array[][], dp[][];
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		T = scan.nextInt();
		
		//배열값 저장.
		array = new int[T][T];
		for(int i=0; i<T; i++) {
			for(int j=0; j<=i; j++) {
				array[i][j] = scan.nextInt();
			}
		}
		//깊이탐색할배열 생성 
		dp =new int [T][T];
		for(int i=0; i<T; i++)
			dp[T-1][i] = array[T-1][i];
			//맨 아래층 값만 저장
		System.out.println(test(0,0));
	}
	
	static int test(int depth, int index) {
		if(depth == T-1) return dp[depth][index];
		
		if(dp[depth][index] == 0) {
			dp[depth][index] = Math.max(test(depth+1, index), test(depth+1, index+1)) + array[depth][index];
		}
		return dp[depth][index];
	}
}

---

6	1932	정수 삼각형
각 층의 모든 칸마다 최댓값을 저장하면서 동적 계획법으로 푸는 문제

import java.util.Scanner;

public class Main {
	static int T;
	static int array[][], dp[][];
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		T = scan.nextInt();
		
		//배열값 저장.
		array = new int[T][T];
		for(int i=0; i<T; i++) {
			for(int j=0; j<=i; j++) {
				array[i][j] = scan.nextInt();
			}
		}
		//깊이탐색할배열 생성 
		dp =new int [T][T];
		for(int i=0; i<T; i++)
			dp[T-1][i] = array[T-1][i];
			//맨 아래층 값만 저장
		System.out.println(test(0,0));
	}
	
	static int test(int depth, int index) {
		if(depth == T-1) return dp[depth][index];
		
		if(dp[depth][index] == 0) {
			dp[depth][index] = Math.max(test(depth+1, index), test(depth+1, index+1)) + array[depth][index];
		}
		return dp[depth][index];
	}
}

---

7	2579	계단 오르기
i번째 계단에 오를 때, 몇 개의 연속한 계단을 올랐는지를 고려하여 부분문제를 정의해봅시다.

import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
      Scanner scan = new Scanner(System.in);
      //입력값 입력받기
      int T = scan.nextInt();
      int array[] =new int [T+1];
      int dp[]= new int [T+1];
      
      for(int i=1; i<=T; i++)
         array[i] = scan.nextInt();
      
      dp[1] = array[1];
      if(T>=2) dp[2] = array[2]+dp[1];
      
      for(int i=3; i<=T; i++) {
    	  dp[i] = Math.max((array[i] + array[i-1] + dp[i-3]), (array[i] + dp[i-2]));
      }
	  System.out.println(dp[T]);
	  
   }
}

---

8	1463	1로 만들기
메모이제이션으로 N을 1로 바꾸기 위해 주어진 연산을 몇 번 사용하는지 계산하는 문제

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bfr.readLine());

		int dp[] = new int[n+1];
		
		//n이 0이거나 1이면 최소횟수=0임
		dp[0] = dp[1] = 0; 

		//n이 2이상이면 셋중에 가장 작은값.
		for(int i=2; i<=n; i++) {
			dp[i] = dp[i-1]+1;
			if(i%3==0) dp[i] = Math.min(dp[i], dp[i/3]+1);
			if(i%2==0) dp[i] = Math.min(dp[i], dp[i/2]+1);
		}
		System.out.println(dp[n]);
	}
}