[백준] 3360 - 깡총깡총 (c++)

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

 

문제 요약

n이 주어진다. 3,2,1로만 증가하지 않는 수열을 만들어 합이 n이 되는 경우의 수를 구해라.

 

풀이 (N/3)

• 수학

제한이 커서 나이브하겐 풀 수 없고 좀 변형해서 풀어야 한다. 2,1만 써서 문제를 풀어보면 경우의 수가 n+1이다. 3은 맨 앞에만 올 수 있기 때문에 3의 개수를 고정하고 2,1만 써서 수열을 만드는 개수의 합을 구해주면 문제를 풀 수 있다.

 

for문 안에서 %연산을 매 번 해주면 시간초과가 난다. 식에서 long long 범위를 초과하지 않는다는 걸 눈치채고 마지막 한 번 만 %연산을 해줘야 한다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e6;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    ll ans=0;
    for(int i=n;i>=0;i-=3)
        ans+=i/2+1;
    cout<<ans%mod;
}