글 읽기 - 도움 부탁드립니다.

operaghost 6년 전 0

시간 복잡도를 줄이기 위하여

***** 체크한 부분을 추가하였습니다.

처음에는 if(x >= 2 * y)로 시도를 해보니 되지 않아서

엉겹결에 3배로 바꾸었더니 통과를 하였습니다.

몇 일동안 첨에 시도한 경우는 왜 되지 않는지 반례를 생각해보았는데

도저히 찾아지지가 않네요.

고수님들의 도움이 필요합니다. ^^

#include <bits/stdc++.h>
#define P 0x7fffffff
using namespace std;
 
int n, m, DT[11111][111];
 
int f(int x, int y){
    if(x <= 0 || y <=0)return P;
    if(x < y)       return f(y, x);
    if(DT[x][y])    return DT[x][y];
    if(x % y == 0)  return x / y;
 
    int &ret = DT[x][y] = DT[y][x];
    ret = P;
 
    if(x >= 3 * y) ret = min(ret, f(x-y, y) + 1); //*****
    else{
        for(int i=1; i<= x / 2; i++)ret = min(ret, f(x - i, y) + f(i, y));
        for(int i=1; i<= y / 2; i++)ret = min(ret, f(x, y - i) + f(x, i));
    }
 
 
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    printf("%d", f(n, m));
    return 0;
}

plzrun 6년 전 6

반례:

36 17
답은 10입니다.
그런데 *2하는 경우 답이 12가 나옵니다.

(한변이 9짜리인 정사각형이 4개, 8짜리가 4개, 4짜리가 2개 => 10개)

*3으로 처리하면 처음 자를 때

이거말고도 인풋데이터 넣고 비교해보니까 들어가는 인풋 100만개 중 반례데이터는 9495개가 있네요.

몇 개 더 나열해 볼게요.

N M (*3인 경우(정답), *2인 경우(오답))
52 25 (11, 12)
53 17 (11, 13)
60 29 (12, 17)
10000 49 (216, 217)

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

문제

문제

출처

ICPC

도움 부탁드립니다.

operaghost 6년 전 0

plzrun 6년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말