godvicii   4년 전

궁금함에 잠을 설쳐 다시 재x2 질문드립니다. 


구현 방식은 DP로 i를 1씩 증가시키면서 잘려진 두 부분의 합과 기존의 합중 작은것을 선택하는 방식으로 풀었습니다.

음. 우선 이문제는 시간초과와의 사투였습니다. 아래 조건을 넣기 전까지는 말이죠.

이 질문의 예전에 하신분것을 보니(물론 그 글에도 답변은 달려있지 않아서..)


if(큰변 > 작은변*3)


절을 추가해서 돌려보았더니 얼떨떨하게 통과하였습니다. 뭐지?

또한 if(큰변 > 작은변*(3이상의수)) 도 마찬가지였습니다.

솔루션에는 if(큰변*3>작은변*작은변) 조건이 추가되어있더군요.

저 조건이 특히 *3 이부분이 왜 들어갔을때 통과했는지 모르겠네요..


시간을 단축시킬수있는 다른 조건이 더 있다면 알려주시면 너무 감사하겠습니다... (꾸벅)

처음 구현할 때

무조건 작은 변으로 정사각형을 하나 만드는 조건으로 구현 하였더니

if (큰변 > 작은변 ) 일때,  D[M][N] = MIN(D[M][N], solve(M-N, N) + 1);

이였는데 '8 7' 과 같은 반례가 있었습니다. 

그래서 아예 조건을 빼고 돌렸더니 시간초과가 났네요..('5119 99' 와 같은 인풋시)

고수님들의 가르침 부탁드립니다.

아래는 시간초과 나는 소스입니다.

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