루고 문제에 대한 제 해법입니다.

문제의 핵심은 신호등의 수가 2025개라는 점에서 출발하며, 이때 시간 복잡도가 O(n^2)보다 작은 동적 계획법(DP)을 고려해야 합니다.

각 조작 후 불이 켜진 횟수와 초기 상태 간의 차이를 상태로 설정하면 편리합니다. 첫 번째 조작 후 상태는 0으로 시작합니다. 여기서 dp[i][j]는 (i+1)번째 조작 후 상태 j를 가질 경우의 수를 나타냅니다.

문제의 요구 사항은 정확히 세 가지 다른 값의 불빛 수를 갖는 것이므로, 상태 집합은 중복되지 않는 세 가지 요소를 가져야 합니다. 각 조작은 단지 한 개의 불빛 상태만 변경하므로 가능한 상태 변화는 +1(꺼짐에서 켜짐) 또는 -1(켜짐에서 꺼짐)입니다. 따라서 다음과 같은 두 가지 규칙을 도출할 수 있습니다:

• 상태 집합은 {0,1,2}, {-1,0,1}, {-2,-1,0} 중 하나일 수 있습니다.
• dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1].

위 규칙을 바탕으로 [0,2], [-1,1], [-2,0] 범위에서 DP를 실행하고 결과값을 더하면 됩니다.

그러나 테스트케이스에서 오류가 발생합니다. 이를 해결하기 위해 중복된 두 요소 상태 집합을 제거해야 합니다. 즉, [0,1]과 [-1,0] 범위에서 DP를 실행하여 해당 경우의 수를 빼야 합니다.

시간 복잡도는 O(n).

다음은 C++ 코드 예시입니다:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, MOD = 1e9 + 7;
int n = 2025;

ll solve(int range_start) {
    ll dp[N][3] = {};
    dp[0][range_start + 1] = 1;
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
        dp[i][2] = dp[i - 1][1];
    }
    return (dp[n][0] + dp[n][1] + dp[n][2]) % MOD;
}

int main() {
    ll result = (solve(0) + solve(-1) + solve(-2)) % MOD;
    result = (result - 2 * (solve(-1) + solve(0)) % MOD + MOD) % MOD;
    cout << result << '\n';
    return 0;
}

Python 버전의 코드는 다음과 같습니다:

MOD = 10**9 + 7
n = 2025

def dp_calc(start):
    dp = [[0] * 3 for _ in range(n + 1)]
    dp[0][start + 1] = 1
    for i in range(1, n + 1):
        dp[i][0] = dp[i - 1][1] % MOD
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD
        dp[i][2] = dp[i - 1][1] % MOD
    return (dp[n][0] + dp[n][1] + dp[n][2]) % MOD

result = (dp_calc(0) + dp_calc(-1) + dp_calc(-2)) % MOD
result = (result - 2 * (dp_calc(-1) + dp_calc(0)) % MOD + MOD) % MOD
print(result)