[BOJ] 백준 1904번 - 01타일(with Java)

알고리즘

N=1부터 N=8까지의 각각의 경우에 대해서 만들 수 있는 가짓수를 계산해보면 아래와 같이 도출된다. 결과를 보게 되면 3번째항부터는 이전 항과 그 이전 항을 더해서 만들어지는 피보나치 수열임을 알 수 있다.

 

따라서 N=1, N=2일 때는 정답을 각각 1과 2로 출력해주고, N=3 이상부터는 i-2번째와 i-1번째 항을 더해서 i번째 항을 구하면 된다. N은 최대 백만까지 가능하므로 15746으로 나눠줘야만 하는데, 정답을 도출할 때 나눠주게 되면 이미 오버플로우가 발생한 상태로 결과가 나오게 된다. 이를 방지하기 위해서는 i-2번째 항과 i-1번째 항을 합해준 후에 15746을 나눈 값으로 i번째 항을 구해주면 문제가 해결된다.

소스코드

문제링크

1904번: 01타일