글 읽기 - 10803 질문입니다.

chatterboy 8년 전 4

아래와 같이 코드를 짜고 TLE를 받은 후에 솔루션을 찾아봤는데

if (3 * i >= j*j) R[i][j] = R[i-j][j] + 1;

와 같은 조건문이 추가로 있더라구요.. 왜 하필 3*i >= j*j 인지를 모르겠습니다. ㅠㅠ

#include<cstdio>
#include<algorithm>
using namespace std;

int n, m, dp[10002][102];

int main() {
	for(int i = 1; i < 10001; ++i)
		for(int j = 1; j < 101; ++j) dp[i][j] = 987654321;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j) {
			if(i == j) {
				dp[i][j] = 1;
			} else {
				for(int k = 1; i >= 2*k; ++k)
					dp[i][j] = min(dp[i][j], dp[k][j]+dp[i-k][j]);
				for(int k = 1; j >= 2*k; ++k)
					dp[i][j] = min(dp[i][j], dp[i][k]+dp[i][j-k]);
			}
		}
	printf("%d", dp[n][m]);
}

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

문제

문제

출처

ICPC

10803 질문입니다.

chatterboy 8년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말