SWEA 22039. 피보나치 수 분배

피보나치 수열이 i>2 , fi = fi-1 + fi-2 인데, 1, 2, …, N을 두 개의 집합 A, B로 분할해서, ∑a∈Aƒ­a = ∑­b∈Bƒb를 만족시키는 게 가능한지 확인하고, 가능하다면 분할 방법을 출력하는 문제이다. 불가능하면 impossible을 출력한다.

 

fi = fi-1 + fi-2 이므로 두 집합으로 균등 분할한 결과는 짝수이기 때문에 N % 3 이 1이면 항상 홀수가 되어 균등 분할할 수 없게 된다.

N%3 == 2 라면 2를 만들어야 하므로 f1 + f2를  의미하게 되어 BA 혹은 AB를 앞에 붙여준다. 나머지 수 들은 균등 분할에 의해 BA를 붙였다면 BBA, AB를 붙였다면 AAB로 길이가 N이 될 때 까지 채워준다.

if (n % 3 == 1) {
    sb.append("impossible").append('\n');
    continue;
}
int count = 0;
if (n % 3 == 2) {
    sb.append("BA");
    count += 2;
}
while (count < n) {
    sb.append("BBA");
    count += 3;
}

 

 

결과 코드는 다음과 같다.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (tc-- > 0) {
            int n = Integer.parseInt(br.readLine());
            if (n % 3 == 1) {
                sb.append("impossible").append('\n');
                continue;
            }
            int count = 0;
            if (n % 3 == 2) {
                sb.append("BA");
                count += 2;
            }
            while (count < n) {
                sb.append("BBA");
                count += 3;
            }
            sb.append('\n');
        }

        br.close();
        System.out.print(sb);
    }
}