글 읽기 - 틀린점을 못찾겠습니다.

mygm1302 5년 전 0

알고리즘 자체는 L모양의 종이를 한번 그어 쪼개는 모든 경우의수에 대해 재귀적으로 계산했습니다.

직사각형 종이와 L모양 종이로만 쪼개지기 떄문에, 이걸 이용해 재귀했습니다

혼자 해결해보려고 테케를 20개 넘게 넣어봤는데 반례를 찾지 못해 수정하지 못했습니다.

도움 부탁드립니다..

#include <iostream>
#include <string.h>
#include <climits>
using namespace std;
int dp[51][51][51][51];
int dp2[51][51];
int minPieceI(int H,int W);
int minPieceL(int H,int W,int h,int w){
	int temp=INT_MAX;
	if(dp[H][W][h][w]!=-1)return dp[H][W][h][w];
	for(int i=1;i<H-h;i++)
		temp=min(minPieceL(H-i,W,h,w)+minPieceI(i,W),temp);
	for(int i=1;i<h;i++)
		temp=min(minPieceL(H-i,W,h-i,w)+minPieceI(i,W-w),temp);
	for(int i=1;i<W-w;i++)
		temp=min(minPieceL(H,W-i,h,w)+minPieceI(H,i),temp);
	for(int i=1;i<w;i++)
		temp=min(minPieceL(H,W-i,h,w-i)+minPieceI(H-h,i),temp);
	temp=min(temp,minPieceI(H-h,W)+minPieceI(h,W-w));
	temp=min(temp,minPieceI(H,W-w)+minPieceI(H-h,w));
	dp[H][W][h][w]=temp;
	dp[W][H][w][h]=temp;
	return temp;
}
int minPieceI(int H,int W){
	if(dp2[H][W]!=-1)return dp2[H][W];
	if(H==0 || W==0)return 0;
	int big=max(H,W);
	int small=min(H,W);
	dp2[H][W]=big/small+minPieceI(big%small,small);
	dp2[W][H]=dp2[H][W];
	return dp2[H][W];
}
int main(){
int H,W,w,h;
	memset(dp,-1,sizeof(dp));
	memset(dp2,-1,sizeof(dp2));
	cin>>H>>W>>h>>w;
	cout<<minPieceL(H,W,h,w);
	return 0;
}

mygm1302 5년 전 0

5 10 1 4

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

문제

문제

출처

ICPC

틀린점을 못찾겠습니다.

mygm1302 5년 전 0

mygm1302 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말