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

Drabina라는 문제인데 사다리 한 번에 1개 ~ 2개씩 오를 수 있고,

N번째 사다리에 오를 수 있는 경우의 수를 2^p로 나눈 나머지가 몇인지 물어보는 간단한 피보나치 문제임

근데 수 제한이 테케 100만, N 100만이라 풀기 전에 dp[N]을 전부 구해놓고 푸는데도 계속 시간초과가 난다..


http://boj.kr/55afc378418948fc909c7f75503a5f10

int main() { // p값 미리 정해줌 bases[0] = 1; for (int i = 1; i <= 31; i++) { bases[i] = bases[i - 1] * 2ll; } // 피보나치 구하기 dp[1] = 1; dp[2] = 2; for (int i = 3; i <= 1000000; i++) { dp[i] = (dp[i - 1] + dp[i - 2]) % bases[31]; } // 문제 쿼리 int ts; cin >> ts; for (int t = 1; t <= ts; t++) { int s, p; cin >> s >> p; cout << dp[s] % bases[p] << '\n'; } return 0; }

내가 푼 링크인데 너무 쉬운 문제라 간단하게 주석만 해놨어..

갑자기 착한 일 하고싶어진 피붕이들은 와서 좀 도와줘..