[JAVA] 백준 14651번 : 걷다보니 신천역 삼 (Large)

 

---

 

• 생각

 

1이 입력되면 정답 : 0
2가 입력되면 정답 : 2
3이 입력되면 정답 : 6
4가 입력되면 정답 : 18

 

여기까지 해보면 대충 감이 온다. 3부터 i의값은 i-1값의 3을 곱한 값이다. 한번 확인해보니 정답이 다 떨어져 맞았다.

3을 곱하다보면 숫자가 너무커져 int형을 벗어날 수 있으니 long타입으로 배열을 만들어야한다.

 

• 코드

정답 코드 : 점화식으로 푼 코드이다.

 

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

public class Main {
	static int N;
	static long[] array;

	public static void main(String[] args) throws Exception {
		SetData();
        Calculate();
		System.out.println(array[N] % 1000000009);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        N = Integer.parseInt(br.readLine());
        array = new long[33334];
	}

    private static void Calculate(){
    	array[1] = 0;
        array[2] = 2;        

        for (int i = 3; i <= N; i++)
                 array[i] = (array[i - 1] * 3) % 1000000009;
    }
}