Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 문자열
  • 이분탐색
  • 백준
  • 누적합
  • 브루트포스
  • 위상 정렬
  • KMP
  • 백트래킹
  • UC++
  • 트라이
  • 조합론
  • 정렬
  • LCA
  • 큐
  • 트리
  • 세그먼트 트리
  • 투포인터
  • 유니온 파인드
  • 분할정복
  • 우선순위큐
  • 정수론
  • 최소 스패닝 트리
  • 구현
  • 수학
  • 그래프
  • 기하
  • SCC
  • C++
  • 동적계획법
  • 스택

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite
공부 및 정리/백준 코드

[C++]백준 - 2170번 문제

[C++]백준 - 2170번 문제
공부 및 정리/백준 코드

[C++]백준 - 2170번 문제

2021. 11. 15. 19:17

2170번: 선 긋기 (acmicpc.net)

 

2170번: 선 긋기

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

www.acmicpc.net

 

2170번 : 선 긋기


매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

 

입력


첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력


첫째 줄에 그은 선의 총 길이를 출력한다.

 

 


 

생각해 볼 점


스위핑 알고리즘을 쓰는 문제입니다.

 

스위핑 기법(Sweeping Algorithm) (수정: 2019-06-24) : 네이버 블로그 (naver.com)

 

스위핑 기법(Sweeping Algorithm) (수정: 2019-06-24)

안녕하세요 겁나 오랜만입니다. 종강 기념으로 드디어 새 글을 씁니다. (하지만 아직도 바쁩니다.) 이번에 ...

blog.naver.com

 

알고리즘은 위 블로그에서 설명이 잘 되어 있습니다.

 

풀이도 기법 그대로 사용하므로 생략합니다.

 

코드


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

int main()
{
	int N;
	scanf("%d", & N);

	unsigned int result = 0;
	vector<pair<int, int>> vec;
	for (int i = 0; i < N; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		vec.push_back({ x, y });
	}

	sort(vec.begin(), vec.end());

	int x = -1000000000, y = -1000000000;
	for (pair<int, int> p : vec)
	{
		if (y < p.first)
		{
			result += y - x;
			x = p.first;
		}
		if (y < p.second) y = p.second;
	}
	result += y - x;

	printf("%d", result);
	return 0;
}

 

그 외


 

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 11004번 문제  (0) 2021.11.16
[C++]백준 - 2836번 문제  (0) 2021.11.15
[C++]백준 - 1620번 문제  (0) 2021.11.12
[C++]백준 - 1004번 문제  (0) 2021.11.12
[C++]백준 - 2162번 문제  (0) 2021.11.11
  • 2170번 : 선 긋기
  • 입력
  • 출력
  • 생각해 볼 점
  • 코드
  • 그 외
'공부 및 정리/백준 코드' 카테고리의 다른 글
  • [C++]백준 - 11004번 문제
  • [C++]백준 - 2836번 문제
  • [C++]백준 - 1620번 문제
  • [C++]백준 - 1004번 문제
Plite
Plite
개발 일지, 게임 이야기 등을 적어두는 공간입니다.

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.