유형별 문제풀이 tony - 동적계획법2

주지수

• 문제
• 코드

풀이

• 처음에 행별로 누적값을 계산한 후 구했더니 시간초과. 아예 처음부터 직사각형의 합을 누적합으로 저장해줘야했다.
• 계산을 편하게 하기 위해 가로 세로 모두 한 줄씩 더 크게 만들고 첫행은 전부 0으로 나머지 열도 첫 칸은 전부 0으로 초기화 해줬다.
• 데이터 값을 저장할 때 (1,1)에서 해당 칸 까지 직사각형을 그렸을 때의 합을 저장해줬다.
  • 저장 방식 윗칸 + 왼쪽칸 - 대각선칸 + 자신의 값
• 들어온 값을 계산 해줄 때 아래 그림처럼 파란 네모의 값을 구하고자 했다면 빨간 네모 빼고 초록네모 빼고 겹치는 분홍 네모 값을 더해주는 방식으로 구했다.