백준 3037 / C++

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

3037번: 혼란

 

[ 풀이 ] 

dp[i][j]를 1~i까지 혼란도가 j인 수열의 개수라고 정의하자.

1~i번 칸에서 수 i를 놓는 위치를 생각해보자. 

i를 k번 칸에 놓았다면, k+1칸~i번 칸에 의해 혼란도가 i-k개 증가한다.   

따라서 i를 k번 칸에 놓을 때 혼란도가 j가 되려면 k번칸을 제외한 1~i-1에서 혼란도가 j-(i-k)가 되어야 한다.

따라서 식은 dp[i][j]=sum(dp[i-1][j-i+k])이다. 식을 더 개선해보자. 

dp[i][j]와 dp[i][j-1] 차를 구하면, dp[i-1][j]-dp[i-1][j-i]가 됨을 알 수 있다.

따라서 dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-i]가 된다. 

식을 계산시 i와 i-1만 보므로 토글링으로 공간을 줄여주자. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, c, dp[2][10001];
const ll mod = 1e9 + 7;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> c;
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		dp[i%2][0] = 1;
		for (int j = 1; j <= c; j++) {
			dp[i%2][j] = (dp[i%2][j-1]+dp[1-i%2][j]-(j>=i?dp[1-i%2][j-i]:0)+mod)%mod;
		}
	}
	cout << dp[n%2][c];
}