글 읽기 - 정사각형 만들기 틀렸습니다. 도와주세요.

rdd6584 6년 전 0

정사각형을 하나씩 만들면서 잘라갔거든요.

시간초과에 걸릴 지 언정, 틀렸습니다는 나와선 안된다고 생각하는데, 52%에서 틀렸습니다가 나오네요.

혹시 반례가 있을까요?

한 변의 길이가 i인 정사각형을 하나 그리고 남은 부분을 직선으로 좍좍 짤랐을때, 2가지 경우중에 최솟값을 반환하는 것으로 했습니다

#include<stdio.h>

int dp[10001][101] = { 0 };
int go(int n, int m) {
	if (n == 0 || m == 0) return 0;
	int t;
	if (m > n) { t = m; m = n; n = t; }
	if (dp[n][m]) return dp[n][m];
	int mn = 99999999, temp = 99999999;

	for (int i = m; i >= 1; i--) {
			temp = go(i, m - i) + go(n - i, m);
			if (temp < mn) mn = temp;
			temp = go(i, n - i) + go(m - i, n);
			if (temp < mn) mn = temp;
	}

	return dp[n][m] = mn + 1;
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	printf("%d", go(n, m));
}

nuclear852 5년 전 0

저도 52%에서 틀렸습니다 나오는데 어떻게 해결하셨는지 힌트좀 부탁드릴게여

rdd6584 5년 전 3

저 로직으로는 반례가 있는 것으로 확인되었습니다. 지금은 생각이 안나는군요.

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

문제

문제

출처

ICPC

정사각형 만들기 틀렸습니다. 도와주세요.

rdd6584 6년 전 0

nuclear852 5년 전 0

rdd6584 5년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말