[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)2502번, 떡 먹는 호랑이

문제 링크

2502번: 떡 먹는 호랑이

---

 

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 호랑이는 어제와 그저께 받은 떡의 개수를 더한 만큼 떡을 가져갑니다.

2. 첫 번째날 떡의 개수 ≤ 두 번째날 떡의 개수가 만족해야 합니다.

3. D번째 날 할머니가 K개의 떡을 주었을 때 첫 날과 둘째 날 준 떡의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 피보나치를 이용하여 둘째 날 떡의 개수를 구합니다.

 

3. 첫 날 떡의 개수와 둘째 날 떡의 개수를 결과로 출력합니다.

 

 

피보나치를 이용한 탐색!

 

첫 날의 떡의 개수 : x

 

둘째 날의 떡의 개수 : y

 

셋째 날의 떡의 개수 : x + y

 

넷째 날의 떡의 개수 : x + 2y

 

....

 

4번째 날부터 얻을 수 있는 떡의 개수의 점화식

 

(n-1)번째 떡의 개수가 ax + by이면

 

n번째 떡의 개수 : bx + (a+b)y

 

예를 들어 5번째 떡의 개수를 구할 때

 

4번째 떡의 개수 : x + 2y

a : 1

b : 2

 

점화식 적용

5번째 떡의 개수 : 2x + (1 + 2)y  : 2x + 3y

 

D번째 떡의 개수를 구한 뒤

 

ax + by = K

 

a가 0이 되지 않는 y의 최대값을 구합니다.

 

y가 될 수 있는 값의 조건 : (K - by) % a == 0

 

해석 : (K - by)이 a로 나누어떨어지면 x도 자연수의 값을 가지기 때문에 y의 값은 성립!

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

D = 7

K = 218

 

2. 피보나치를 이용하여 둘째 날 떡의 개수를 구합니다.

 

7번째 날의 떡의 개수 구하기!

 

[1] : x[2] : y

 

[3] : x + y

 

[4] : x + 2y

 

[5] : 2x + 3y

 

[6] : 3x + 5y

 

[7] : 5x + 8y = 218

 

7번째 떡의 개수를 구한 뒤 y의 최대값 구하기!

 

y에 들어갈 수 있는 값 : {27, 26 , ......., 1}

 

27일 때 : 5x = 218 - 216 = 2

x = 2/5 : 자연수 X 실패!

 

26일 때 : 5x = 218 - 208 = 10

x = 2 : 자연수 O 최대값 구하기 성공!

 

3. 첫 날 떡의 개수와 둘째 날 떡의 개수를 결과로 출력합니다.

 

첫 날 떡의 개수(x) : 2

둘째 날 떡의 개수(y) : 26

 

2 26 28 54 82 136 218

 

2

26

을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용해서 D, K를 띄어쓰기 기준 나누었습니다.
• D번째 떡의 개수를 ax + by의 형태로 구합니다.
• y에 들어갈 수 있는 값들을 탐색하여 x가 자연수가 되는 최대값을 구합니다.
• x의 값과 y의 값을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int D = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        //넘어온 날이 3일일 때
        if(D == 3)
            bw.write( 1 + "\n" + (K-1));
        else{	//3일보다 클 때
            int x = 1, y = 1;	// x + y
            //D번째 떡의 개수 ax + by 형태 구하기
            for(int i=4;i<=D;i++){
                int temp  = y;
                y = x + y;
                x = temp;
            }
            int size = K/y;	//y 입력 가능한 최대값
            //x가 자연수가 되는 y의 최대값 탐색!
            for(int i = size-1;i>=0;i--){
                if((K - (i*y)) % x == 0){	//x가 자연수가 되는 y의 최대값 성립!
                    //x의 값과 y의 값 BufferedWriter 저장
                    bw.write( (K - (i*y)) / x+ "\n" + i);
                    break;
                }
            }
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}