[BOJ] 18291 - 비요뜨의 징검다리 건너기

문제 출처

백준 18291 - 비요뜨의 징검다리 건너기

 

풀이

비요뜨가 1번 징검다리에서 마지막 징검다리까지 도달하여 강을 건너는데 경우의 수를 구하는 문제였습니다.

 

경우의 수가 2^N-2의 규칙을 가지고 있고  

징검다리의 개수가 최대 10⁹까지 이기 때문에  

그대로 계산한다면 10⁹ + 7로 나눈다고 해도  너무 큰 수가 되버려 long long 범위를 넘어가버립니다.

 

따라서 (2⁸) -> ((2²)²)² 이런 식으로 재귀함수를 돌려 계산해주었습니다.

 

코드

small-j/BOJ_Algorithm