본문 바로가기

분류 전체보기167

강의실 배정 #11000 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 100MB 10^9 Si Ti 를 인덱스로 담기 불가능하다. 그럼 DP는 아니고, Greedy이다. 수업 시작시간, 끝시간을 기준으로 sorting하는 것은 O(logN=200000) 이므로 연산시간이 적으니, 부담없이 사용할 수 있다. 조건 1. Ti b; } //long long arr[1000000000]; int main() { int n; ios::sync_with_stdio(fa.. 2023. 11. 23.
로프 #2217 c++ 풀이 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 아직 그리디라는 것이 와닿지는 않지만 문제를 풀어보는 중이다. 보자마자 음.. 최소값에 개수를 곱하면 가장크지 않을까? 라는 생각이 들었고, 그렇게 코딩해서 1틀림 그리고 생각해보니까 sort한 v[i]번째값에 n-i 개를 곱한 것도 비교해야 한다는 것을 알았다. #include #include #include using namespace std; int main() { int n; ve.. 2023. 11. 22.
행렬 #1080 c++ 풀이 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 내가좋아하는 행렬 문제 근데, 왜 Greedy알고리즘인지 모르고 풀었다. 검사해서 3개씩 바꿀건데 바꾸기전과 바꾼후가 다르면 결국 변환시킬수 없는 것이다. 따라서, 우선 변환시키고 다르면, 변환했을때를 비교해서 검사했다. #include using namespace std; int arr[51][51]; int answer[51][51]; int N, M; int cnt; void change(int y, in.. 2023. 11. 22.
신입사원 #1946 c++ 풀이 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net dp를 어느정도 감을잡고 greedy를 푸는 중이다. 1 4 2 3 3 2 4 1 5 5 로 sort후, 뽑힌 사람들을 확인하니 두번째 요소에 대해 내림차순인 것들만 count 해주면 된다. 솔직히 이게 왜 greedy인지 모르겠다. #include #include #include #include using namespace std; int main() { int T; cin.. 2023. 11. 22.

티스토리툴바