240 words
1 minutes
[BOJ] 성인 게임
| TimeLimit | MemoryLimit | Condition | TAG |
|---|---|---|---|
| 1s | 1024MB | (1≤T≤1,000 1≤N≤1,000,000) | Dynamic Programming |
우왕… 약간 처음보는 유형이라 조금 해매긴 했습니다. 나눠서 푸는 이런 느낌 오호 재밌었습니다. 이게 칼날이 막대기로 나오냐 아니냐 요걸로 나눠서 풀면 됩니다.
생각보다 어려웠따! 넵
아 그리구 식이 길어지니까 vim으로 하다가 이제 약간 IDE가 얼마나 편한지 알았습니다. 제가 원래 Xcode를 쓰고 있었는데… 그것도 기능이 참 많은 거였네요 허헣
정답 코드
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 1000000007;
int t, n;
ll dp[2][1'000'001];
void solve() {
dp[0][0] = 1;
dp[0][1] = 7;
dp[1][1] = 3;
for(int i = 2; i < 1'000'001; i++) {
dp[0][i] = ((3 * dp[0][i-1]) % mod + (4 * dp[1][i-1]) % mod) % mod;
dp[1][i] = (dp[0][i-1] + (2 * dp[1][i-1]) % mod) % mod;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
solve();
while(t-->0) {
cin >> n;
cout << dp[0][n] << "\n";
}
return 0;
}