[Python] BOJ(백준) 11659, 11660번 - 구간 합 구하기(4), (5)

1. 구간 합 구하기 4

https://www.acmicpc.net/problem/11659

난이도(solved.ac 기준): 실버3

풀이

간단한 DP 문제다. DP 배열 값은, 이전 인덱스의 값에 + 이전 인덱스의 input값으로 받은 리스트 값을 더해주면 된다. 구간을 더해준 뒤 dp[목적지점] - dp[시작지점-1] 을 해주면 해결할 수 있다. 이 부분은 직접 dp값을 출력해보는 게 더 와닿을 것이다.

여기에서 sys.stdin.readline을 사용하지 않으면 무조건 시간 초과가 난다. 따라서 sys.stdin.readline을 반드시 써야 한다.

2. 구간 합 구하기 5

https://www.acmicpc.net/problem/11660

난이도(solved.ac 기준): 실버1

풀이

1번의 구간 합 구하기 4의 2차원 버전이라고 생각하면 된다. 선이 면으로 바뀌었다. 우선 누적합 DP는 현재 위치 기준 위 행의 값과 왼쪽 열의 값을 더해주면 된다. 하지만 이렇게 할 경우 그림처럼 겹치는 부분이 두 번 더해진다. 따라서 그 부분을 빼주면 된다.

이게 가능한 이유는 DP 배열 자체가 누적합이기 때문이다. 기본적으로 누적합은 그 면에 도달하기 위한 두 가지 경로(보통 왼쪽에서 오른쪽, 위에서 아래로 가므로 이 기준대로 한다면 (위 + 왼)의 값)의 값을 더해주는 방식이다. 따라서 겹치는 부분만 빼주면 되는 것이다.

 

이제 누적합에 대한 설명은 되었으므로 구간의 합을 어떻게 구할지에 대해서 알아보자.

그림과 같이 구하고 싶은 구간 합이 있다고 해 보자. 우리는 6칸의 합을 구해야 한다. 여기에서 참고할 부분의 사각형을 보자. 위에서 DP의 값을 구했던 방식과 동일하다. 6칸의 합을 구하기 위해 6칸 전부를 건드리는 것이 아니라, 12칸에서 8칸을 빼주는 방식을 사용할 것이다. 왜냐면 말했다시피 DP는 누적합이기 때문.

 

1번은, 1번까지 해당하는 모든 값들의 합이다. 여기에서 2번과 3번을 빼주고 4번을 더해주면 된다. 우선 4번을 더해주는 이유는 2번과 3번의 과정에서 4번의 블록이 겹치기 때문이다. 그리고, 2번과 3번은 각각 그 위치까지의 누적합에 해당한다. 따라서 이 부분을 빼줘야 순수한 6칸만의 누적합을 구할 수 있게 된다. 이 방식은 각 6칸의 값이 무엇인지를 확인하는 과정을 거치지 않는다.

이를 코드로 나타낸 것이 위 코드이다. 여기에서 (x1, y1)이 4번에 해당하고 (x2, y2)가 1번에 해당한다.