[백준] 1451 직사각형으로 나누기 in Python

이번 문제는  구현하기 좀 까다로웠다 !! 2차원 배열을 제대로 연습할 수 있는 징한 구현문제이다

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

1451번: 직사각형으로 나누기

 

1. 직사각형을 나누는 방법은 총 6개다 

  

1) 세로로 3분할

2) 가로로 3분할

 

 

이렇게 6가지이다. 

3) 전체 세로분할 후 가로분할 

4) 전체 세로분할 후(R1, R3), 가로분할(R2)

5) 전체 가로분할 후(R1), 세로분할 (R2,R3)

6) 전체 가로분할 후 (R1, R2), 세로분할 (R1, R3)

 

주의할 점 !

어쨌든 직사각형을 이루는 단위는 1*1 정사각형 한칸이므로 좌표를 구할 때 주의해야 한다.

예를 들어서, 6)의 R3에서 좌측 상단 점 (x1, y1) 는 (1, j+1)이다. 왜냐하면 R1의 가장 마지막 좌표가 j 였으니까, 실질적으로 한칸을 차지하므로 +1을 해줘야 한다 

 

2. 분할한 직사각형들의 합을 구하는 법 

i) 직사각형 칸 (1, 1) ~ (i, j) 의 합을 s[i][j]에 저장해두면 전체 합을 구하기 편리하다.

s[i][j] = (1, 1) ~ (i, j) 까지 합

s[i][j] = s[i-1][j] + s[i][j-1] + sum[i-1][j-1] + data[i][j] // data는 입력되는 전체 직사각형 정보를 저장한 2차원 리스트

 

ii) cal_sum() 함수 -> R1, R2, R3의 영역 각각의 합을 구하기 위한 함수

(x1,y1) (x2, y2) 좌표를 파라미터로 가진다.각각의 좌표는 자른 직사각형의 좌측 상단, 우측 하단 좌표이다. 

* (x1,y1) ~ (x2, y2) 합 구하기 

s[x2][y2] : (1,1) ~ (x2,y2) 전체 직사각형에 있는 숫자들의 합

s[x2][y1 - 1] : 노란색 영역 

s[x1 - 1][y2] : 파란색 영역

s[x1 - 1][y1 - 1]: 노란색 영역과 파란색 영역이 겹치는 부분

구하려는 영역: 보라색으로 색칠한 (x1,y1) ~ (x2, y2)

s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] 

https://www.slideshare.net/Baekjoon?utm_campaign=profiletracking&utm_medium=sssite&utm_source=ssslideview

 

Baekjoon Choi

위는 백준님 풀이!! 이걸 참고 했다