[백준] 15922 아우으 우아으이야!!

백준 15922 아우으 우아으이야!! 문제 풀이입니다.

아우으 우아으이야!!

이 문제는 제목이 너무 신기해서 풀어봤습니다…ㅎㅎ

가끔 보면 백준엔 재밌고 신선하고 참신한 문제가 많은거 같았습니다. 이래야 푸는 재미가 있죠 ㅎㅎ

이 문제는 그냥 이중포문으로 풀게되면 누가봐도 시간초과가 나올만한 범위를 가지고 있습니다.

따라서 저는 이분탐색을 사용하여 문제를 해결하였습니다.

때마침 입력도 정렬되서 들어왔기 때문에 따로 데이터 전처리라던가 정렬을 해줄필요가 없었습니다.

원리는 입력받는 x,y 값을 보면서 겹치는지 안겹치는지를 확인하며 left right값을 갱신하고 값을 업데이트 하면 됩니다.

소스코드는 다음과 같습니다.

Source Code:

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

#define INF 1000000000

int N;

int main() {
	cin >> N;

	long long answer = 0;
	long long left = -INF;
	long long right = -INF;


	for (int i = 0; i < N; i++) {
		long long a, b;
		cin >> a >> b;

		if (a > right) {
			answer += (right - left);
			left = a;
			right = b;
		}
		else {
			right = max(right, b);
		}

	}
	answer += (right - left);
	cout << answer;

	system("pause");
	return 0;
}
}

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 되도록이면 푼 문제들 계속 올리도록 하겠습니다…
• 또 간혹 설명이 이해가 안간다면 말해주시면 그림까지 같이 넣는 노력을 하겠습니다. 감사합니다.