글 읽기 - 이 문제 탑다운으로는 못 푸나요?

knight7024 3년 전 0

TLE가 나옵니다.

일반적으로 탑다운이 바텀업보다 속도가 더 걸리는 건 알고 있는데

탑다운으로는 못 푸는 건지 아니면 어떻게 수정을 하면 좋을지 조언 부탁드리겠습니다.

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define MOD 1000000007
using namespace std;

string s;
// [A][B]: A번째의 구문의 인덴트가 B일 때의 경우의 수
int dp[5001][5001];

int dfs(int idx, int tab) {
	if (idx == s.size() - 1) return 1;
	int& ret = dp[idx][tab];
	if (ret) return ret;

	int result = 0;
	// 반복문이 열리면
	if (s[idx] == 'f') {
		// 한 칸 인덴팅 시킨다.
		result = dfs(idx + 1, tab + 1) % MOD;
	}
	// 실행문이 열리면
	else {
		// 처음부터 현재까지 들어갈 수 있는 모든 실행문 찾는다.
		for (int i = 0; i <= tab; i++) {
			result = (result % MOD + dfs(idx + 1, i) % MOD) % MOD;
		}
	}

	return ret = result;
}

int main() {
	cin >> s;

	cout << dfs(0, 0);

	return 0;
}

mym0404 2년 전 0

탑다운이 문제라기보단 지금 코드의 시간복잡도가 O(N^3) 이라서 못풉니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 문제 탑다운으로는 못 푸나요?

knight7024 3년 전 0

mym0404 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말