melon940925   4년 전

더이상 줄일 방법이 안떠오르는데

for문에서 뭔가 낭비되는 연산이 있는걸까요?

vkdldjdos   3년 전

조금 오래됐지만 그래도 혹시 저같은 분들이 계실까봐 써놓습니다..

dp를 일부분 도입해야합니다

31번째 줄에서 for 루프를 통해 해당 행의 모든 원소를 더해주고 있는데 이부분이 중복연산이 많은부분이라 따로 처리 안해주면 시간초과 나기가 쉽더라구요


임의의 2차원배열 sub[401][801] 을 생성해서 해당 행의 부분합들을 따로 저장해 놓으면 연산이 빨라집니다.


예를들어 sub[10][3] 은 10행의 1번쨰 2번째 3번째 원소들의 합을 갖고있습니다.


이를 통해서 31번째 for 루프에서 j 에서 j+2K 까지 2K번의 덧셈의 연산을

sub[y][j+2K] - sub[y][j-1] 을 통해 1번의 연산으로 알아낼수있지요

melon940925   3년 전

질문글을 올려놓고 깜빡하고있었네요 ㅎㅎ..

저는 이미 해결했지만

다른 분들이 이 글을 보고 도움을 받으셨으면 합니다

답변 감사합니다!

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