[C++] 백준 7579: 앱
문제 이해- 현재 N개의 앱, A1, ..., An이 활성화 되어있다.- 이들 앱은 각각 mi바이트만큼 메모리를 사용한다.- 각 앱을 다시 실행하고자 할 때 ci의 비용이 들어간다.- N개의 앱 중 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 확보하고자 할 때, 비용 ci의 합을 최소화하는 방법을 구하라. - 시간 제한: 1초- 메모리 제한: 128MB - N: 활성화된 앱의 개수 (1 ~ 100, 10^2)- M: 필요한 메모리의 크기 (1 ~ 10,000,000, 10^7)- mi: Ai가 사용중인 메모리의 바이트 크기 (1 ~ 10,000,000, 10^7)- ci: Ai를 비활성화 했을 때 비용 (0 ~ 100, 10^2)※ M - 필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최..
[C++] 백준 1717: 집합의 표현
문제 이해- 초기에 n+1개의 집합이 있다.- {0}, {1}, ..., {n}- 합집합 연산과 두 집합이 같은 집합에 포함되어 있는지 확인하는 연산이 존재한다.- 집합을 표현하는 프로그램을 작성하라. - 시간 제한: 2초- 메모리 제한: 128MB - n: 집합의 개수 관련 변수 (1 ~ 1,000,000, 10^6)- m: 연산의 개수 (1 ~ 100,000, 10^5)- 연산: 합집합(0 a b), 같은 집합에 포함되어 있는지 확인(1 a b) - 1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 yes, 있지않으면 no를 출력하라. 문제 풀이두 원소가 같은 집합에 속하는지 아닌지를 판단하는 유니온 파인드의 기본 문제이다. 유니온 파인드 알고리즘은 같은 집합에 속하는 원소들..