[boj : 2459] 철사 자르기

www.acmicpc.net/problem/2459

2459번: 철사 자르기

문제 : 철사를 판에 맞게 따라서 쭉 놓는다. 이때 격자에서만 꺾을 수 있다.(꺽기는 격자의 좌표는 순차적이다). 철사를 자를 l 이 주어지고 l 과 l+1 사이를 자른다. 최대의 길이를 가진 철사를 구해라

 

풀이 : 

철사가 잘리는 좌표만 잘 처리하여 하나씩 저장해 주자.

x<=l && l<y 의 조건에 만족을 한다면 철사가 잘리게 된다.

이때 가장 중요한 점은 절대로 절대로 double 형 즉, 실수로 계산하여 처리하지 말아라.

이유는 우리가 보지 못하는 어느 곳에서 실수형의 수가 의도한 바와 달리 조금의 오차가 발생하여 저장될 수 있기 때문이다. (필자는 이때문에 좀 해맸다)

 

소스 :

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

vector<pair<ll, ll>> v;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	ll n, k, l;
	cin >> n >> k;

	v.resize(k + 2);
	for (ll i = 1; i <= k; i++)
		cin >> v[i].first >> v[i].second;
	cin >> l;

	//(1,1) 부터 시작 해서 (1,1)로 돌아옴
	v[0].first = v[0].second = 1;
	v[k + 1].first = v[k + 1].second = 1;

	ll cnt = 0;
	vector<ll> ans;

	for (ll i = 1; i <= k + 1; i++) {
		ll x = v[i - 1].first;
		ll y = v[i].first;

		if (x > y)swap(x, y);
		//잘려진 철사의 개수 count
		if (x <= l && l < y)
			cnt++;
	}
	ans.resize(cnt + 1);
	ll pos = 0;
	for (ll i = 1; i <= k + 1; i++) {
		ll x = v[i - 1].first;
		ll y = v[i].first;

		if (x > y)swap(x, y);
		//만약 잘려진 부분에 포함이 되면 나눠서 계산
		if (x <= l && l < y) {
			pos++;
			if (v[i - 1].first < v[i].first) {
				ans[pos - 1] += abs(v[i - 1].first - l) * 2 + 1;
				ans[pos] += abs(v[i].first - l - 1) * 2 + 1;
			}
			else {
				ans[pos - 1] += abs(v[i - 1].first - l - 1) * 2 + 1;
				ans[pos] += abs(v[i].first - l) * 2 + 1;
			}
		}
		//아니라면 가로/세로 길이 계산
		else {
			if (v[i - 1].first == v[i].first)
				ans[pos] += abs(v[i - 1].second - v[i].second) * 2;
			else
				ans[pos] += abs(v[i - 1].first - v[i].first) * 2;
		}
	}
	//for (ll i = 0; i < ans.size(); i++)
	//	cout << ans[i]<<" ";

	//맨처음과 마지막은 용접으로 연결되어있음
	ans[0] += ans[cnt];
	ll Max = -1;
	for (ll i = 0; i < cnt; i++)
		Max = max(Max, ans[i]);
	cout << Max / 2;

	return 0;
}