백준 9625 BABBA

문제

설명

처음에는 아래와 같이 잘못 접근하였다. 

1 - A

2 - B

3 - BA

4 - BAB

5 - BABBA

6 - BABBAB

 

다시 보니, 말 그대로 A는 B로, B는 BA로 바꾸라는 것이었다.

1 - A

2 - B

3 - BA

4 - BAB

5 - BABBA

6 - BABBABAB

 

A와 B의 갯수를 세어보니 A는 A끼리, B는 B끼리 피보나치 수열의 형태로 A[n] = A[n-2] + A[n-1] 형식으로 구성되어 있는 것을 확인할 수 있었다. 

A B

1 0

0 1

1 1

1 2

2 3

3 5

 

A 1 0 1 1 2 3

B 0 1 1 2 3 5 

 

그래서 A[N] = A[N-2] + A[N-1] 형식으로 값을 구하도록 코드를 구현하였다. 

코드

package Baekjoon;

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

public class BOK_1009 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int loop = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < loop; i++) {
            long result = 1;
            StringTokenizer st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            for (int j = 0; j < b; j++) {
                result = (result * a) % 10;
            }
            if(result == 0) sb.append("10").append("\n");
            else sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}