BOJ2167 (1) 썸네일형 리스트형 [BOJ][DP] 2167. 2차원 배열의 합 문제 -> https://www.acmicpc.net/problem/2167 그림을 그려서 생각을하면 간단히 풀리는 문제. (애초에 문제는 거의 다 그림으로 풀지만..) 이 문제의 설명이 오해의 소지가 있다..[i][j] 부터 [x][y]까지의 합이라는 의미는 아래의 의미다.처음에 잘 못 이해하는바람에 왜 틀리는지 이해가 안갔었다. 그냥 무작정 (i, j) ~ (x, y)의 합을 구해도 정답이 뜬다고는 하는데, 시간복잡도가 점점 커질 수 밖에 없다. 그래서 효율적으로 각 dp배열에 (1,1)부터 자신까지의 합을 구해놓는다. 그러믄, 합을 구하는 점화식을 생각해보자. 빨간색 체크표시가 된 위치를 dp[x][y]라 치자. 각각 다른색으로 칠해진 사각형은 이미 구해진 dp 값이다.일단 더하자.dp[x][y] .. 이전 1 다음
