[BOJ] 13270번 - 피보나치 치킨 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

계속 풀어보았지만 실패해서 다른 사람의 풀이를 참고한 내용을 바탕으로 내가 이해한 내용을 정리한다.

처음에는 사람 수, 치킨 수의 피보나치 수열을 분리해서 생각하여 이에 대한 연관성을 생각하지 못했다.

 

그러나 위의 그림과 같이 두 변수 a와 b가 있다고 생각해보자.

처음 a와 b가 1닭 2인을 나타내고 있으면 다음 a와 b의 값은 2닭 3인이 되어야한다.

즉, a = b, b = a+b 로 값이 변한다는 것이다.

 

여기서 우리가 구해야할 것은 최소 치킨 수와 최대 치킨 수이다.

• min 배열 : min[i] 는 i인분 시켰을 때 최소 치킨 수
• max 배열 : max[i] 는 i인분 시켰을 때 최대 치킨 수

단,  이 배열은 항상 길이가 3이상일 것이다. 또한 [0, 1번 인덱스 : 0명, 1명]는 사용이 불가능하다. → N >= 2

그러나 우리는 계산을 위해서 0명일 경우 치킨의 수 0으로 설정해둔다.

주의할 점은 min 배열의 1명의 인덱스는 큰 값으로 저장해두는데 이는 홀수명 일때 잘못된 계산을 하지 못하도록 하기 위함이다.

예를 들어 3명일 경우 3인 2닭만 가능한데 2인1닭 + 1인 0닭 으로 잘못된 계산이 이루어질 수 있다.

max의 경우는 어차피 가능한 큰 수로 들어가기 때문에 따로 처리해줄 필요가 없다.

 

이와 같은 성질을 이용하여 b = 2일 때 (→ 2인 1닭으로 시킬 경우) 부터 차례차례 계산해보는 것이다.

6일 경우 min, max 배열 변화

while(b <= n) {
	for(int i = b; i <= n; i++) {
		min[i] = Math.min(min[i], min[i-b] + a);
		max[i] = Math.max(max[i], max[i-b] + a);
	}
	int tmp = b;
	b += a;
	a = tmp;
}

DP를 이용하여 현재 b인 a닭으로 우리가 구해야할 n인분의 치킨 마리수를 구하는 것이다.

• b =  현재 몇명분의 세트인지 나타내는 변수
• a =  그 세트에 들어있는 닭의 수를 나타내는 변수
• i = 몇 인분을 시켜야할지 나타내는 변수, 이는 항상 b <= i <= n 조건을 만족한다.
• i-b = i인분 중 b인분을 제외한 인분 = b인 a닭을 시키면 i인분을 만족 = m[i-b] + a

이번에는 거의 해석하는 시간이 되었던 것 같다.

코드를 읽고 동작 원리는 무엇이고 왜 이렇게 해야하지? 라는 고민을 하게 만든 문제였다.

다음에는 직접 풀 수 있도록 노력해야겠다.

---

🍀 풀이 🍀

package Baekjoon;

import java.io.*;

public class DP13270 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine()); //사람 수 (n >= 2)

        int a = 1; //1닭 -> 피보나치 수열의 첫번째 항
        int b = 2; //2인 - > 피보나치 수열의 두번째 항

        int[] min = new int[n+1]; //min[i] : i명일 때 최소의 치킨 수
        int[] max = new int[n+1]; //max[i] : i명일 때 최대의 치킨 수

        for(int i = 1; i <= n; i++) {
            min[i] = 987654321;
        }

        while(b <= n) {
            for(int i = b; i <= n; i++) {
                min[i] = Math.min(min[i], min[i-b] + a);
                max[i] = Math.max(max[i], max[i-b] + a);
            }
            int tmp = b;
            b += a;
            a = tmp;
        }
        bw.write(min[n] + " " + max[n]);
        bw.flush();
        bw.close();
    }
}