발효홍삼
코딩하는 홍삼
발효홍삼
전체 방문자
오늘
어제
  • 분류 전체보기 (142)
    • PS (63)
      • 프로그래머스 (9)
      • 코드업 (10)
      • 백준 (43)
      • 알고스팟 (1)
    • Programming Language (11)
      • html_css (2)
      • java (0)
      • c,c++ (2)
      • vanillajs (2)
      • react (0)
      • vue.js (0)
      • angular.js (0)
      • electron (3)
      • 엄랭(Umjunsik-lang) (1)
      • F# (1)
      • Node.js (0)
      • Go (0)
    • knowledge (41)
      • algorithm (3)
      • data structure (1)
      • os (1)
      • ML (1)
      • math (31)
      • paper review (0)
      • IT-license (4)
    • Programming Guide (27)
      • React (1)
      • Electron (2)
      • CSS , SASS ( SCSS ) , Tailw.. (3)
      • Node.js (1)
      • Go (1)
      • Ruby on Rails (2)
      • R (1)
      • PHP (1)
      • Docker (1)
      • JSP (1)
      • C# (1)
      • Django (1)
      • Flask (1)
      • Dart (1)
      • Next.js (1)
      • Vue.js (1)
      • Unity (1)
      • React Native (0)
      • Flutter (3)
      • GraphQL (1)
      • MongoDB (1)
      • .NET (1)
      • RUST (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • c++
  • 미적분학
  • 이산수학
  • 수학
  • java
  • electron
  • 적분
  • 기초백제
  • nodejs
  • codeup
  • CSS
  • JavaScript
  • 출력
  • C
  • HTML
  • 미분
  • 구현
  • Python
  • 파이썬
  • 프로그래머스
  • 코드업
  • 정보처리기능사
  • cpp
  • LV1
  • 정보처리기능사 필기
  • 자바
  • js
  • 기초100제
  • 알고리즘
  • 백준

최근 댓글

최근 글

티스토리

250x250
hELLO · Designed By 정상우.
발효홍삼

코딩하는 홍삼

[ 백준 ] 1931번 : 회의실 배정 - ( C++/C , JAVA/자바, PYTHON/파이썬 )
PS/백준

[ 백준 ] 1931번 : 회의실 배정 - ( C++/C , JAVA/자바, PYTHON/파이썬 )

2022. 2. 25. 05:05
728x90
  • 문제

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

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net


  • 풀이법 ( 알고리즘 )

https://kim6394.tistory.com/67 글을 참조하였다.

 

시작 시간이 빨라도 종료 시간이 늦게 끝나면 최대 회의 수를 가질 수 없다.

따라서 vector 컨테이너에 회의의 시작 시간과 종료 시간을 저장한 후 정렬을 한다.

 

이때 끝나는 시간이 같다면 시작하는 시간이 빠른 순으로 정렬하고, 끝나는 시간이 같지 않다면 종료 시간이 빠른 순으로 정렬한다.

 

그리디는 최선의 선택을 한다는 점이 어렵게 다가오는 거 같다.


  • 풀이 - C++ ( C )
더보기
#include <iostream>
#include <algorithm> // sort
#include <vector> 

using namespace std;

int n; // n : 회의의 수

struct Time {
	int start;
	int end;
};

bool compare(Time x, Time y) {
	if (x.end == y.end) // 끝나는 시간이 같다면
		return x.start < y.start; //시작하는 시간이 빠른 순으로 정렬 
	else return x.end < y.end; // 종료시간이 빠른 순으로 정렬
}

int main(void)
{
	//input
	cin >> n;

	//solve
	vector <Time> schedule(n);
	for (int i = 0; i < n; i++)
		cin >> schedule[i].start >> schedule[i].end;

	sort(schedule.begin(), schedule.end(), compare); //정렬

	int cnt = 0; // 회의 가능한 수
	int ending_time = 0; // 회의의 종료 지점

	for (int i = 0; i < schedule.size(); i++)
	{
		if (ending_time <= schedule[i].start) // 회의의 종료 시점이 다음 회의의 시작지점보다 빠르면
		{
			ending_time = schedule[i].end; // ending_time에 다음 회의의 종료 시점 저장
			cnt++;
		}
	}

	//output
	cout << cnt;
	return 0;
}
  • 풀이 - JAVA
더보기
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[][] schedule = new int[n][2]; // schedule[][0] : 시작지점 , schedule[][1] : 종료지점
		
		for(int i = 0; i < n; i++) {
			schedule[i][0] = sc.nextInt();
			schedule[i][1] = sc.nextInt();
		}
		
		Arrays.sort(schedule, new Comparator<int[]>() {
			
			@Override 
			public int compare(int[] x, int[] y) {
				
				//끝나는 시간이 같은 경우
				if(x[1] == y[1]) return x[0] - y[0]; // 시작 시간이 빠른 순 정렬
				else return x[1] - y[1];
			}
		});
	
		int cnt = 0;
		int ending_time = 0;
		
		for(int i = 0; i < n; i++)
		{
			//전 회의의 종료시간이 다음 회의의 시작시간보다 작거나 빠르다면 갱신
			if(ending_time <= schedule[i][0])
			{
				ending_time = schedule[i][1];
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}

}
  • 풀이 - PYTHON
더보기
n = int(input())

schedule = []

for _ in range(n):
    start, end = map(int,input().split())
    schedule.append((start,end))

schedule = sorted(schedule, key = lambda a:a[0])
schedule = sorted(schedule, key = lambda a:a[1])

cnt = 0
before_end = 0

for start,end in schedule:

    if start >= before_end:
        cnt += 1
        before_end = end

print(cnt)

 

728x90
저작자표시 비영리 (새창열림)

'PS > 백준' 카테고리의 다른 글

[ 백준 ] 14888번 : 연산자 끼워넣기 - ( C++/C , PYTHON/파이썬, JAVA/자바 )  (0) 2022.02.25
[ 백준 ] 4948번 : 베르트랑 공준 - ( C++/C , JAVA/자바, PYTHON/파이썬 )  (0) 2022.02.25
[ 백준 ] 2581번 : 소수 - ( C++/C , JAVA/자바, PYTHON/파이썬 )  (0) 2022.02.25
[ 백준 ] 7568번 : 덩치 - (C++/C , JAVA/자바 , PYTHON / 파이썬)  (0) 2022.02.25
[ 백준 ] 2302번 : 극장 좌석 - (c++/c, java/자바, python/파이썬)  (0) 2022.02.17
    'PS/백준' 카테고리의 다른 글
    • [ 백준 ] 14888번 : 연산자 끼워넣기 - ( C++/C , PYTHON/파이썬, JAVA/자바 )
    • [ 백준 ] 4948번 : 베르트랑 공준 - ( C++/C , JAVA/자바, PYTHON/파이썬 )
    • [ 백준 ] 2581번 : 소수 - ( C++/C , JAVA/자바, PYTHON/파이썬 )
    • [ 백준 ] 7568번 : 덩치 - (C++/C , JAVA/자바 , PYTHON / 파이썬)
    발효홍삼
    발효홍삼
    코딩하는 홍삼

    티스토리툴바