[λ°±μ€€ 1931] νšŒμ˜μ‹€ λ°°μ •(C++)

2023. 10. 26. 14:29Β·πŸ–₯️ Study Note/Coding Test

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

 

1931번: νšŒμ˜μ‹€ λ°°μ •

(1,4), (5,7), (8,11), (12,14) λ₯Ό μ΄μš©ν•  수 μžˆλ‹€.

www.acmicpc.net

문제

ν•œ 개의 νšŒμ˜μ‹€μ΄ μžˆλŠ”λ° 이λ₯Ό μ‚¬μš©ν•˜κ³ μž ν•˜λŠ” N개의 νšŒμ˜μ— λŒ€ν•˜μ—¬ νšŒμ˜μ‹€ μ‚¬μš©ν‘œλ₯Ό λ§Œλ“€λ €κ³  ν•œλ‹€. 각 회의 I에 λŒ€ν•΄ μ‹œμž‘μ‹œκ°„κ³Ό λλ‚˜λŠ” μ‹œκ°„μ΄ μ£Όμ–΄μ Έ 있고, 각 νšŒμ˜κ°€ κ²ΉμΉ˜μ§€ μ•Šκ²Œ ν•˜λ©΄μ„œ νšŒμ˜μ‹€μ„ μ‚¬μš©ν•  수 μžˆλŠ” 회의의 μ΅œλŒ€ 개수λ₯Ό μ°Ύμ•„λ³΄μž. 단, νšŒμ˜λŠ” ν•œλ²ˆ μ‹œμž‘ν•˜λ©΄ 쀑간에 쀑단될 수 μ—†μœΌλ©° ν•œ νšŒμ˜κ°€ λλ‚˜λŠ” 것과 λ™μ‹œμ— λ‹€μŒ νšŒμ˜κ°€ μ‹œμž‘λ  수 μžˆλ‹€. 회의의 μ‹œμž‘μ‹œκ°„κ³Ό λλ‚˜λŠ” μ‹œκ°„μ΄ 같을 μˆ˜λ„ μžˆλ‹€. 이 κ²½μš°μ—λŠ” μ‹œμž‘ν•˜μžλ§ˆμž λλ‚˜λŠ” κ²ƒμœΌλ‘œ μƒκ°ν•˜λ©΄ λœλ‹€.

μž…λ ₯

첫째 쀄에 회의의 수 N(1 ≤ N ≤ 100,000)이 μ£Όμ–΄μ§„λ‹€. λ‘˜μ§Έ 쀄뢀터 N+1 μ€„κΉŒμ§€ 각 회의의 정보가 μ£Όμ–΄μ§€λŠ”λ° 이것은 곡백을 사이에 두고 회의의 μ‹œμž‘μ‹œκ°„κ³Ό λλ‚˜λŠ” μ‹œκ°„μ΄ μ£Όμ–΄μ§„λ‹€. μ‹œμž‘ μ‹œκ°„κ³Ό λλ‚˜λŠ” μ‹œκ°„μ€ 231-1보닀 μž‘κ±°λ‚˜ 같은 μžμ—°μˆ˜ λ˜λŠ” 0이닀.

좜λ ₯

첫째 쀄에 μ΅œλŒ€ μ‚¬μš©ν•  수 μžˆλŠ” 회의의 μ΅œλŒ€ 개수λ₯Ό 좜λ ₯ν•œλ‹€.

λ‚΄ 풀이

이 λ¬Έμ œλŠ” 그리디 λ¬Έμ œμž„μ„ μƒκ°ν•˜λ©΄μ„œ, λ§€ λ°˜λ³΅λ¬Έλ§ˆλ‹€ 졜적의 ν•΄λ₯Ό κ΅¬ν•˜λ €κ³  κ³ λ―Όν–ˆλ‹€.

ν•œ νšŒμ˜μ‹€μ—μ„œ 회의λ₯Ό 많이 ν•˜κΈ° μœ„ν•΄μ„œλŠ” 회의 μ’…λ£Œ μ‹œκ°„μ΄ λΉ λ₯Έ νšŒμ˜λ“€λ‘œ ꡬ성을 ν•΄μ•Όν•œλ‹€.


과정은 λ‹€μŒκ³Ό κ°™λ‹€.

  1. νšŒμ˜λ“€μ˜ μ‹œμž‘ μ‹œκ°„κ³Ό μ’…λ£Œ μ‹œκ°„μ„ μž…λ ₯ λ°›λŠ”λ‹€.
  2. μ‹œμž‘ μ‹œκ°„μ΄ λΉ λ₯Έ 순으둜 μ •λ ¬ν•΄μ€€λ‹€.
  3. μ •λ ¬λœ 회의 μ‹œκ°„ν‘œλ₯Ό μˆœνšŒν•˜λ©΄μ„œ μ΅œλŒ€ 회의 수λ₯Ό κ΅¬ν•œλ‹€.
    1. 회의 수(max), ν˜„μž¬ 회의 μ‹œμž‘ μ‹œκ°„(curstart), ν˜„μž¬ 회의 μ’…λ£Œμ‹œκ°„(curend)을 μ €μž₯ν•  λ³€μˆ˜ μ„ μ–Έν•œλ‹€.
    2. μƒˆ νšŒμ˜κ°€ ν˜„μž¬ νšŒμ˜μ™€ μ‹œκ°„μ΄ κ²ΉμΉ˜λ©΄μ„œ μ’…λ£Œ μ‹œκ°„μ΄ 더 λΉ λ₯Έ 회의라면
      • ν˜„μž¬ 회의 μ‹œμž‘ μ‹œκ°„κ³Ό ν˜„μž¬ 회의 μ’…λ£Œ μ‹œκ°„μ„ μƒˆ 회의 μ‹œκ°„μœΌλ‘œ κ°±μ‹ ν•œλ‹€.
    3. → μƒˆ 회의λ₯Ό ν˜„μž¬ 회의둜 μ„€μ •
    4. μƒˆ νšŒμ˜κ°€ ν˜„μž¬ 회의 μ’…λ£Œ ν›„ μ‹œμž‘λ˜λŠ” 회의라면
      • 회의 수 +1
      • ν˜„μž¬ 회의 μ‹œμž‘ μ‹œκ°„κ³Ό ν˜„μž¬ 회의 μ’…λ£Œ μ‹œκ°„μ„ μƒˆ 회의 μ‹œκ°„μœΌλ‘œ κ°±μ‹ ν•œλ‹€.
    5. → μƒˆ 회의λ₯Ό λ‹€μŒ 회의둜 μ„€μ •
  4. μ΅œλŒ€ 회의 수λ₯Ό λ°˜ν™˜ν•œλ‹€.
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

int main()
{
	int count;
	vector<pair<int, int>> meetings;
	cin >> count;

	for (int i = 0; i < count; ++i)
	{
		int start, end;
		cin >> start >> end ;
		meetings.push_back({start, end});
	}

	sort(meetings.begin(), meetings.end());
	int max = 0;
	int curstart = 0;
	int curend = 0;
	for (auto m : meetings)
	{
		// νšŒμ˜κ°€ κ²ΉμΉ λ•Œ, λλ‚˜λŠ” μ‹œκ°„μ΄ 더 μž‘μ€ 것을 ν˜„μž¬ 회의둜 μ„€μ •ν•œλ‹€.
		if (curend > m.first)
		{
			if (curend > m.second)
			{
				curstart = m.first;
				curend = m.second;
			}
		}

		// νšŒμ˜κ°€ 겹치치 μ•Šμ„λ•Œ λ‹€μŒ 회의둜 μ„€μ •ν•œλ‹€.
		else
		{
			++max;
			curstart = m.first;
			curend = m.second;
		}
	}

	cout << max << endl;

	return 0;
}
μ €μž‘μžν‘œμ‹œ λΉ„μ˜λ¦¬ λ³€κ²½κΈˆμ§€ (μƒˆμ°½μ—΄λ¦Ό)

'πŸ–₯️ Study Note > Coding Test' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]μœ μ—°κ·Όλ¬΄μ œ(C++)  (0) 2025.04.14
[λ°±μ€€ 1926] κ·Έλ¦Ό(C++)  (0) 2023.11.18
[λ°±μ€€ 1003] ν”Όλ³΄λ‚˜μΉ˜ ν•¨μˆ˜ (C++)  (0) 2023.10.25
[Hacker Rank] Organizing Containers of Balls (C++)  (1) 2023.10.09
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.3 - μΉ΄λ“œ 짝 λ§žμΆ”κΈ°(C++)  (1) 2023.10.05
'πŸ–₯️ Study Note/Coding Test' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
  • [ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]μœ μ—°κ·Όλ¬΄μ œ(C++)
  • [λ°±μ€€ 1926] κ·Έλ¦Ό(C++)
  • [λ°±μ€€ 1003] ν”Όλ³΄λ‚˜μΉ˜ ν•¨μˆ˜ (C++)
  • [Hacker Rank] Organizing Containers of Balls (C++)
Beankong_
Beankong_
μ£Όλ‹ˆμ–΄ ν΄λΌμ΄μ–ΈνŠΈ ν”„λ‘œκ·Έλž˜λ¨Έ 곡뢀 기둝
  • Beankong_
    Beankong's Devlog
    Beankong_
  • 전체
    였늘
    μ–΄μ œ
    • 전체 κΈ€ (146)
      • β›… Daily (0)
      • πŸ–₯️ Study Note (2)
        • C++ (1)
        • Unreal Engine (5)
        • Coding Test (123)
        • Design Patteren (5)
        • VCS (Git..) (1)
        • Server (1)
      • 🧭 Devlog (8)
        • μ˜€λ‹΅λ…ΈνŠΈ (4)
        • UE5 GameLift Server Test Project (1)
        • TIL (3)
  • λΈ”λ‘œκ·Έ 메뉴

    • 링크

    • 곡지사항

    • 인기 κΈ€

    • νƒœκ·Έ

      μ•Œκ³ λ¦¬μ¦˜
      μ΅œλ‹¨ 거리 μ•Œκ³ λ¦¬μ¦˜
      ν”„λ£Œκ·Έλž˜λ¨ΈμŠ€
      unrealengine build system
      OnlineSubsystem
      ν—¬ν…Œμ΄μ»€
      cpp
      κ²Œμž„ 개발
      unrealengine module
      κ²Œμž„ν”„λ‘œκ·Έλž˜λ°
      propertyaccess
      programmers
      κ²Œμž„ ν”„λ‘œκ·Έλž˜λ°
      그리디(greedy)
      ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€
      κ²Œμž„ λͺ¨μž‘
      UnrealEngine5
      κ·Έλž˜ν”„ 순회
      UnrealEngine
      μ½”λ”©ν…ŒμŠ€νŠΈ
    • 졜근 λŒ“κΈ€

    • 졜근 κΈ€

    • hELLOΒ· Designed Byμ •μƒμš°.v4.10.3
    Beankong_
    [λ°±μ€€ 1931] νšŒμ˜μ‹€ λ°°μ •(C++)
    μƒλ‹¨μœΌλ‘œ

    ν‹°μŠ€ν† λ¦¬νˆ΄λ°”