[백준] 2502 떡 먹는 호랑이 - 동적계획법(DP, Dynamic Programming) + 완전탐색(BruteForce) JAVA

https://www.acmicpc.net/problem/2502

코드설명

동적계획법(DP, Dynamic Programming) + 완전탐색(BruteForce)을 활용합니다.

 

 

아떻게 접근했을까요? fibonacci의 아이디어에서 며칠이 지난지 주어지는 입력 A가 몇개의 1일차, 2일차로 이루어지는지 연산했습니다. 

이렇게 할경우 예시로

입력
6 41

출력 (1과 2의 개수)
3 5

입력
7 218

1과 2의 개수
5 8

처럼 나오는 것을 알 수 있습니다.

 

이에 맞추어서 브루트포스로 41을 3과 5로 만드는 모든 방법을 연산시킵니다.

이떄 1 <= A <= B라는 조건이 있으므로, 2중for문으로 연산시켰습니다.

 

처음에 입력2인 아래의 입력이 주어졌을떄

7 218

answer
2
26

답이 2 26 으로 나와서 틀린줄알았으나, 문제예시에 여러개의 답이 존재할 수 있다고 합니다. 그러므로 정답입니다.

코드

정답코드1입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int[] answer = new int[2];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		
		int[] temp = fiboCount(A);
		
		for(int i=1; ; i++) {
			for(int j=i; ; j++) {
				int aNum = i;
				int bNum = j;
				int ret = temp[0] * i + temp[1] * j;
				if(ret > B) break;
				if(ret == B) {
					answer[0] = i;
					answer[1] = j;
					System.out.println(answer[0] + " "+ answer[1]);
					return ;
				}
			}
		}
	}
	
	static int[] fiboCount(int x) {
		if(x == 1) return new int[] {1, 0};
		if(x == 2) return new int[] {0, 1};
		
		int[] ret1 = fiboCount(x - 1);
		int[] ret2 = fiboCount(x - 2);
		int[] ret = new int[] {ret1[0] + ret2[0], ret1[1] + ret2[1]};
		return ret;
	}
	
}

 

메모이제이션 적용한 정답코드2입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int[] answer = new int[2];
	static int[][] cache = new int[31][2];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<31; i++) {
			Arrays.fill(cache[i], -1);
		}
		int[] temp = fiboCount(A);
		for(int i=1; ; i++) {
			for(int j=i; ; j++) {
				int aNum = i;
				int bNum = j;
				int ret = temp[0] * i + temp[1] * j;
				if(ret > B) break;
				if(ret == B) {
					answer[0] = i;
					answer[1] = j;
					System.out.println(answer[0] +"\n"+ answer[1]);
					return ;
				}
			}
		}
		
	}
	
	static int[] fiboCount(int x) {
		if(x == 1) return new int[] {1, 0};
		if(x == 2) return new int[] {0, 1};
		if(cache[x][0] != -1 && cache[x][1] != -1) return cache[x];
		
		int[] ret1 = fiboCount(x - 1);
		int[] ret2 = fiboCount(x - 2);
		int[] ret = new int[] {ret1[0] + ret2[0], ret1[1] + ret2[1]};
		return cache[x] = ret;
	}
	
}