hazxz   7달 전

처음에 생각한건

DT[x][y][k] 라는 배열을 만듭니다.  (x,y)에서 오른쪽 k칸까지 더해서 저장해두는 3차원 배열인데요.

N,M이 최대 300이니깐 300*300*300정도니깐 처음 init 해주고 문제를 풀면 될 것 같았습니다.

답을 출력할때는 i,j,x,y가 입력되면

i~x 까지 각각의 행에서 y-j+1 칸을 더한 값을 DT에서 빼와서 더하면 답이 하나 완성되는 형태로 해서 기본예제case는 맞았습니다.


왜 안되는지 답답해서 그냥 전체탐색법으로 solve2라는 함수를 만들어서 하니 통과하더군라고요.. 대신에 500ms ;;

문제에는 답의 배열의 합이 32bit-int를 벗어나지 않는다고 해서 처음엔 DT를 int 배열로 만들었는데 unsigned를 붙이니 4%인가 8%인가까지 답이 맞는거 같기도 하고..


알고리즘이 틀린건지..아니면 다른 문제가 있는건지 궁금합니다.

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