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

풀이 아이디어

0,1,2로 만들 수 있는 N자리의 3의 배수인 경우의 수를
표현하는 점화식을 찾고 큰 수를 처리하는게 문제 풀이의 핵심이라고 할 수 있다.

어떻게 점화식을 찾았나요? 라고 물어본다면 n=1,2,3,4일 때
0,1,2로 만들 수 있는 3의 배수의 갯수를 직접 구해보았다.

n=1이면 0
n=2이면 2
n=3이면 6
n=4이면 18

점화식으로 표현하면 $f(n) = 2*3^{n-2}$이다.
이때 N의 입력값이 상당히 커서 $2*3^{33331}$를 1,000,000,009로 나눈 나머지도 계산해야했다.
(1 ≤ N ≤ 33,333)

배운 점

JAVA에서 큰 수를 다루는 BigInteger에 대해서 배웠다.
숫자를 문자열로 다루기 때문에 아주 큰 수도 처리할 수 있다.

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        // BigInteger 사칙연산
        BigInteger a = new BigInteger("1234567890");
        BigInteger b = new BigInteger("9876543210");
        
        System.out.println(a.add(b)); // a + b
        System.out.println(a.subtract(b)); // a - b
        System.out.println(a.multiply(b)); // a * b
        System.out.println(a.divide(b)); // a / b
        System.out.println(a.remainder(b)); // a % b
    }
}

$2*3^{33331}$ 같은 큰 숫자를 계산가능하다.
BigInteger의 경우 Math.pow()같은 제곱을 계산해주는 메서드를 사용할 수 없기에
제곱은 for문을 사용해 n-2만큼 해줬다.

풀이 코드

import java.io.*;
import java.math.BigInteger;

public class _14651 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n == 1) {
            System.out.println(0);
            return;
        }
        // 점화식: f(n) = 2*3^(n-2)
        BigInteger numerator = new BigInteger("2");
        for (int i = 0; i < n-2; i++) {
            numerator = numerator.multiply(new BigInteger("3"));
        }
        BigInteger bi = new BigInteger("1000000009");
        System.out.println(numerator.mod(bi));
    }
}