51. 영지(territory) 선택 : (large)

it 취업을 위한 알고리즘 문제풀이

문제

코드1

코드2

문제해결방법1

• 입력 값이 작은 형태에서는 기준 시작 위치부터 주어진 구간의 모든 영역을 하나씩 더하는 방법으로 4중 for문으로 구할 수도 있지만 입력값이 커지면 시간 복잡도가 너무 복잡해진다.
• 이를 해결하기 위해서 입력받으면서 일단 누적합저장할 변수를 새로 만들고 누적합을 구한다. 이때 누적합의 규칙은 i*j 사각형의 격자 까지의 넓이를 구한다.
• 구하는 방법은 다음과 같다.
  • (3,4)까지의 누적합은 "(2,4)까지의 누적합 + (3,3)까지의 누적합 - (2,2)까지의 누적합(중복된부분 제거를 위해 빼줌) + (3,4)현재 위치의 입력값
    

    

• 일반화를 위해서 쓰레기값이 저장된 메모리를 활용하지 않기 위해 2차원 배열의 모든 초기값을 0으로 해준다. (0행과라인과 0열라인의 모든 값이 0이므로 위의 규칙의 일반화 적용이 가능하다.)
• 누적합이 저장된 2차원 배열로 부터 문제의 주어진 구간에서의 합만을 구하기 위해 나머지 부분의 합을 제거해준다.
• 구하는 방법은 아래와 같다.
  • (3,4)부터 문제의 주어진 구간의 우측 대각선 끝은 (4,6)이다. "(4,6)까지의 누적합 - (2,6)까지의 누적합 - (4,3)까지의 누적합 + (2,3)까지의 누적합"

문제해결방법2

• 입력을 모두 받은 후 구하기
• 기준 위치부터 주어진 구간 세로 HH, 가로 HW에 해당하는 넓이를 구하고 한 칸씩 옆으로 추가되는 구간을 더하고(다음 열의 주어진 세로구간까지 모두 합을 더하고) 한칸씩 빠지는 구간을 빼면서(기준점의 주어진 세로 구간 까지의 열을 빼면서) 구한다.
  • 새롭게 더해질 곳은 기준으로부터 현수가 갖게 될 가로길이 만큼 옆으로 간곳, 빠져야 할 곳은 가장 좌측(기준점에서 주어진 세로높이까지의 열)모두
  • "열의 기준점+HW"인 더하고 기준값 빼고 기준 값 다음 열에서 같은 행위 반복
  • (1,1)이 현재 기준일 때 (1,1+HW)더하고 (1,1)은 뺀다. 이같은 행위를 세로HH길이 만큼 반복한다.