BOJ 2597 줄자접기

사용한 알고리즘

구현

알고리즘 설명

줄자를 실제로 접는 듣이 진행하면 된다.
줄자의 중점과 두점을 접었을 때에 좌표가 어떻게 바뀌는지 정의한다.
줄자의 중점을 mid_L 이라고 하고, 접혀저야 하는 부분을 mid라고 할때, mid_L < mid 인 경우 줄자는 오른쪽에서 왼쪽으로 접히며, mid_L > mid 인 경우 줄자는 왼쪽에서 오른쪽으로 접힌다.
이를 이용하면 두가지 경우로 나누어 볼 수 있다.
Case1. 오른쪽에서 왼쪽으로 접히는 경우
1. 접히는 부분의 오른쪽인 경우
  (mid < 좌표 x), (mid,x) -> (mid, mid-(x-mid))
2. 접히는 부분의 왼쪽인 경우 좌표가 옮겨지지 않는다.
  (좌표 x <= mid), (x,mid) -> (x, mid)
Case2. 왼쪽에서 오른쪽으로 접히는 경우
1. 접히는 부분의 오른쪽인 경우
  (mid < 좌표 x), (mid,x) -> (0, x-mid)
2. 접히는 부분의 왼쪽인 경우
  (좌표 x < mid), (x, mid) -> (mid-x, 0)
위 두 알고리즘을 이용하여 3번 접으면 된다.
접은 뒤에 남겨진 줄자는 max(mid, N-mid) 둘 중 하나이다. 값이 mid 인 경우는 Case1, N-mid인 경우는 Case2이다.

풀이

// baekjoon 2597 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<float,float> P;

float N;
P points[3];

int main() {
	scanf("%f", &N);
	for (int i=0; i<3; i++) {
		scanf("%f%f", &points[i].first, &points[i].second);
// 저장 첫번째 요소가 항상 작은 요소로 유지
		if (points[i].first > points[i].second)
			swap(points[i].first, points[i].second);
	}

// 3번 접기 (빨 -> 파 -> 노)
	for (int i=0; i<3; i++) {
// 이미 같은 위치에 있는 경우
		if (points[i].first == points[i].second) continue;
// 두 점의 중간 지점 찾음
		float mid = (float)(points[i].second + points[i].first)/2.f;
// 줄자의 중간보다 오른쪽에 있는 경우 (접으면 줄자의 오른쪽이 남겨짐)
		if (mid < N-mid) { // right
			for (int j=i+1; j<3; j++) {
// 접혀져서 (x, mid) -> (mid-x, 0)형태로 바뀜
				if (points[j].first < mid) points[j].first = mid - points[j].first;
// 이미 오른쪽에 있어서 (mid, x) -> (0, x-mid)
				else points[j].first -= mid;

// 위와 같은 알고리즘
// (y, mid) -> (mid-y, 0)
				if (points[j].second < mid) points[j].second = mid - points[j].second;
// (mid, y) -> (0, y-mid)
				else points[j].second -= mid;
// 접은 뒤에도 첫번째 좌표 < 두번째 좌표 를 유지시킴
				if (points[j].first > points[j].second)
					swap(points[j].first, points[j].second);
			}
			N = N-mid;
// 줄자의 중간보다 왼쪽에 있는 경우 (접으면 줄자의 왼쪽이 남겨짐)
		} else { // left
			for (int j=i+1; j<3; j++) {
// (mid, x) -> (mid, mid-(x-mid))
				if (mid < points[j].first) points[j].first = mid - (points[j].first - mid);
				if (mid < points[j].second) points[j].second = mid - (points[j].second - mid);
// 나머지 경우 (x, mid) -> (x, mid)로 유지되어 아무것도 하지 않아도 됨

// 접은 뒤에도 첫번째 좌표 < 두번째 좌표를 유지시킴
				if (points[j].first > points[j].second)
					swap(points[j].first, points[j].second);
			}
			N = mid;
		}
	}
	printf("%.1f\n", N);
	return 0;
}