[BOJ] 1117 색칠 1

문제 링크

 

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

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

이 문제는 가로로 접는 선 f를 기준으로 왼쪽 종이와 오른쪽 종이의 크기에 따라 두 가지 경우로 나눠볼 수 있다. 두 경우에서 색칠되는 영역의 넓이를 구한 뒤, 이를 전체 영역 넓이에서 빼면 색칠되지 않은 영역의 넓이를 구할 수 있다.

 

1. 왼쪽 크기 <= 오른쪽 크기(f <= w/2)

   오른쪽 종이에 색칠되는 영역은 (x2-x1) * (y2-y1) * (c+1)로 구할 수 있다.

   1-1. 색칠 범위에 왼쪽 종이가 포함되지 않는 경우

         이 경우 접는선 f는 x1보다 작거나 같아야 한다. -> f<=x1

       

   1-2. 색칠 범위에 왼쪽 종이가 포함되는 경우

         이 경우 f는 x1보다 커야 한다. 이때 왼쪽 종이에 색칠되는 영역의 가로 길이는 min(f, x2) - x1이며, 세로 길이는             y2 - y1이다. 이만큼의 영역이 c+1번만큼 칠해진다. 따라서 왼쪽 영역에서 색칠된 영역의 넓이는  

(min(f, x2) - x1) * (y2 - y1) * (c+1)

 

x1이 1, x2가 2일 때, min(f, x2) = 2이므로 왼쪽에 색칠되는 영역의 가로 크기는 2 - 1 = 1이다.

x1이 0, x2가 1일 때 min(f, x2) = 1이므로 왼쪽에 색칠되는 영역의 가로 크기는 1 - 0 = 1이다.

2. 왼쪽 크기 > 오른쪽 크기 (f > w/2)

   왼쪽 종이에 색칠되는 영역은 (x2-x1) * (y2-y1) * (c+1)로 구할 수 있다.   

   2-1. 색칠 범위에 오른쪽 종이가 포함되지 않는 경우

         이 경우 x1 + f는 w보다 작거나 같아야 한다.

x1 + f = 6 이고, w=6이므로 x1 + f <= w이다.

   2-2. 색칠 범위에 오른쪽 종이가 포함되는 경우

       이 경우 x1 + f는 w보다 작아야 한다. 이때 오른쪽 종이에 색칠되는 영역의 가로 길이는 min(w, f + x2) - (f + x1)이

       며, 세로 길이는  y2 - y1이다. 이만큼의 영역이 c+1번만큼 칠해진다. 따라서 왼쪽 영역에서 색칠된 영역의 넓이는  

(min(w, f + x2) - (f + x1)) * (y2 - y1) * (c+1)

f + x2 = 8, w = 6이므로 min(w, f + x2) = 6, 따라서 오른쪽에 색칠되는 영역의 가로 길이는 6 - 5 = 1

 

위의 경우들을 코드로 변환하면 문제를 해결할 수 있다. 이때 전체 종이의 크기가 최대 10억 X 10억이므로 overflow가 발생하지 않도록 long long 형을 사용한다. 전체 코드는 아래와 같다.

 

#include <iostream>
using namespace std;

typedef long long ll;
int main() {
	ll w, h, f, c, x1, y1, x2, y2;
	cin >> w >> h >> f >> c >> x1 >> y1 >> x2 >> y2;
	ll area = (x2 - x1) * (y2 - y1) * (c+1);
	if (f <= w / 2) { //왼쪽 크기 <= 오른쪽 크기
		if (f <= x1) { //왼쪽 영향 X
			cout << w*h - area;
		}
		else { //왼쪽 영향 받음
			cout << w * h - (area + (min(f, x2) - x1) * (y2 - y1) * (c+1));
		}
	} 
	else { //왼쪽 크기 > 오른쪽 크기
		if (w <= x1 + f) { //오른쪽 영향 X
			cout << w * h - area;
		}
		else { //오른쪽 영향 받음
			cout << w * h - (area + (min(w, f + x2) - (f + x1)) * (y2 - y1) * (c+1));
		}
	}
}