파이썬에서는 들여쓰기로 문법이 적용된다.
for문과 state문 여부가 주어질 때 나타날 수 있는 경우의 수를 구하는 문제이다.
풀어놓고 한번 제출했는데 "메모리초과가 나네? 어차피 틀릴거 놨둬야지" 라고 생각하고 제출안했다...
$dp[idx][level]$ : $idx$에서 들여쓰기가 $level$일 때 경우의 수
$s[idx][level]$ : $idx$에서 $level$부터 N까지 경우의 수의 합
4가지 경우([이전,현재]) 로 나누어 생각해 보았다.
1. [f,f]인 경우
for문 두 번이 연속으로 되어있는 경우는 바로 다음 줄로 이어가야한다.
따라서 $dp[idx][level] = dp[idx-1][level-1]$
2. [s,f]인 경우
state문 다음에 for문이 오므로 state문에 도달한 level 이전까지로 다음 for문이 나타날 수 있다.
$dp[idx][level] = s[idx - 1][level]$
3. [f,s]인 경우
for문다음에 state문이 오면 다음 줄로 이어가야한다.
1과같은 경우가 될수밖에 없다.
4. [s,s]인 경우
2와 같은 경우가 된다.
여기서 2,4인 경우를 구하기 위해 누적 경우의 수를 구해야한다.
누적 경우의 수를 bottom-up방식으로 하면 누적 경우의 수를 구해놓을 수 있다.
#include <cstdio>
#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <iomanip>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define mt(a,b,c) mp(a,mp(b,c))
#define mf(a,b,c,d) mp(mp(a,b),mp(c,d))
#define mod (ll)(1e9+7)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
int dy[] = { 0, 0, 1, -1 }; //동, 서, 남, 북
int dx[] = { 1, -1, 0, 0 };
int N;
char t[5022];
ll dp[5022][5022];
ll s[5022];
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf(" %c", &t[n]);
dp[0][0] = 1;
for (int idx = 1;idx < N;idx++) {
memset(s, 0, sizeof s);
for (int level = N - 1;level >= 0;level--) {
s[level] += s[level + 1] % mod + dp[idx - 1][level] % mod;
s[level] %= mod;
}
for (int level = 0;level < N;level++) {
if (t[idx] == 'f') {
if (t[idx - 1] == 'f') {
if (level - 1 >= 0) {
dp[idx][level] += dp[idx - 1][level - 1];
dp[idx][level] %= mod;
}
}
else {
dp[idx][level] += s[level];
dp[idx][level] %= mod;
}
}
else { // 's'
if (t[idx - 1] == 'f') {
if (level - 1 >= 0) {
dp[idx][level] += dp[idx - 1][level - 1];
dp[idx][level] %= mod;
}
}
else {
dp[idx][level] += s[level];
dp[idx][level] %= mod;
}
}
}
}
ll ans = 0;
for (int level = 0;level < N;level++) {
ans += dp[N - 1][level];
ans %= mod;
}
printf("%lld\n", ans);
return 0;
}
| cs |
dp도 거의 top-down방식으로 사용하는데 bottom-up방식도 연습해놔야겠다.
댓글 없음:
댓글 쓰기