조금 오래됐지만 그래도 혹시 저같은 분들이 계실까봐 써놓습니다..
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 4년 전 1
더이상 줄일 방법이 안떠오르는데
for문에서 뭔가 낭비되는 연산이 있는걸까요?