[ boj : 3360 ] 깡총깡총

www.acmicpc.net/problem/3360

3360번: 깡총깡총

문제 : 3,2,1 칸 만큼만 점프가 가능하고 N을 만들려고 하는데 '증가하지 않는 수열' 형태로 만들 수 있는 경우의 수를 구하시오

 

해설 : 흠....전 어려웠습니다 ㅠㅠㅠ

단순 dp로 접근하려고 하면 절대 안되죠 10이 맥시멈이니깐

 

일단 '증가하지 않는 수열'의 의미를 생각해 보면 3x + 2y +z = N 의 형태로 식을 세울 수 있습니다.

여기서 z는 굳이 신경을 써줄 필요가 없죠. 1의 집합이니까요

 

그럼 3x+2y만 신경쓰면 되는데 단순 이중 for문으로 해결하려고 하면 시간초과가 발생하게 됩니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MOD = (ll)1e6;

int main()
{
	ll n;
	cin >> n;

	int ans = 0;
	for (ll x = 0; x <= n; x++) {
		if (3 * x > n)break;
		for (ll y = 0; y <= n; y++)
		{
			if (3 * x + 2 * y > n)break;
			if (ans >= MOD - 1)ans %= MOD;
			ans++;
		}
	}
	cout << ans;
	return 0;
}

그럴수 밖에 없겠죠. 그럼 이 소스를 가지고 다시 생각해 봐야하는데 어느 한쪽을 우린 한번 '고정'을 시켜봅시다.

즉, x를 고정시켜보는 거에요. 이뜻은 N-3*x 만 가지고 생각해 보자는 거고

우린 이 N-3*x 일때 2와 1로만 주어진 집합의 개수를 O(1)의 시간에 알 수 있습니다.

바로 (N-3*x)/2 + 1을 하면 되죠.

왜냐?

2로 나누면 2와 1로만 이루어진 집합이 주어지고 2->1+1 의 형태로 변환을 시킬 수 있으니 결국 2로 나눈 몫만큼 경우의 수가 존재하게 됩니다.(주의할 점은 2가 하나도 없는 경우의 수도 있으니 +1 을 해주어야 합니다)

 

근데 문제가 있는데 매 연산마다 모듈러 연산을 취해주게 되면 tle가 발생하게 됩니다.ㅠㅠ 왜냐면 모듈러 연산 자체가 굉장히 느리다고 하네요. 어차피 최대 정답이 될 수 있는 범위가 long long 형을 넘어서게 되진 않으니 전부 더해준 다음에 그냥 모듈러 연산을 취해주면 답을 도출 할 수 있습니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MOD = (ll)1e6;

int main()
{
	ll n;
	cin >> n;

	ll ans = 0;
	for (ll x = 0; x <= n; x++) {
		if (3 * x > n)break;
		ans += (n-3*x) / 2 + 1;
	}
	cout << ans%MOD;
	return 0;
}