백준 11726번 : 2*n 타일링

2 * 1 크기일 경우

 1개

 

2 * 2 크기일 경우

 2개

 

2 * 3 크기일 경우

 3개

 

2 * 4 크기일 경우

 5개

 

이 문제를 해석해보면 결국, 피보나치수열임을 알 수가 있다.

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n  = sc.nextInt();
		int a = 0;
		int b = 1;
		int result = 1;
		int bi = Integer.MAX_VALUE/2;
		for(int i=1;i<n;i++) {
			a = b;
			b = result;
			if( b > bi ) {
				a = a % 10007;
				b = b % 10007;
			}
			result = a + b;
		}
		System.out.println(result%10007);
	}
}

 

전에 풀었던 dyii.tistory.com/4?category=0 이 문제와는 달리, 10007로 나눈 나머지를 출력한다고 나와있다.

 

1000까지 더할 수 있다보니 integer의 범위를 훌쩍 넘겨버리기 때문에, 마지막 결괏값만 나누는 것이 아니라 연산 중간에도 나머지로 출력해줘야 한다.

 

for 문 내내 10007로 나누었더니 너무 느리게 결과가 나와서

특정 숫자를 넘으면 나누어주는 코드를 추가했다.

 

여기에서 주의할 사항으로는 a가 아니라 b가 특정 숫자를 넘도록 해주어야 한다.

 

둘 다 동시에 10007로 나누어야 하기 때문에 a로 크기를 비교하게 되면, b가 값을 초과하게 되는 경우가 생길 수 있기 때문이다.