[BOJ 1904번] 01 타일(JAVA)

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

1904번: 01타일

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
		int n=Integer.parseInt(br.readLine());
		long num[]=new long[n];
		if(n==1) {
			System.out.println(1);
			return;
		}
		else if(n==2) {
			System.out.println(2);
			return;
		}
		num[0]=1;
		num[1]=2;
		for(int i=2;i<n;i++) {
			num[i]=(num[i-1]+num[i-2])%15746;
		}
		System.out.println(num[n-1]);
	}
}

 이 문제의 결과값을 써서 나열해보면

n=1일 때 1

n=2일 때 2

n=3일 때 3

n=4일 때 5

n=5일 때 8 ...

이런 값이 나옵니다.

이 결과값들이 익숙해보이시는 분들도 있으실 텐데요, 피보나치의 수열을 떠올리시면 좋을 것 같습니다.

현재 값이 전 값과 전전 값의 합으로 이뤄집니다.

저는 num이라는 정수 배열에 값을 저장했는데요, i번째 결과값은 num[i]=num[i-1]+num[i-2]으로 표현할 수 있습니다.

따라서 이를 토대로 코드를 작성하면 위와 같이 코드를 작성할 수 있습니다.

그리고 주의하실 점은 최종적으로 값을 표시할 때 num[i]%15746으로 하셔도 되는데, for문 안에서 중간 중간의 num값들도 15746의 나머지로 저장을 하는 것이 오버플로우도 방지하고, 빠른 계산이 가능하도록 하기 때문에 좋습니다.