본문 바로가기
반응형

Algorithm_BOJ(백준)/그리디(Greedy Algorithm)

 (20)
[백준 13458 python파이썬] 시험 감독 문제 링크 www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제 접근 // 접근: 총감독관은 각 시험관 마다 1명씩 존재한다. // 접근: 시험 감독의 최소 수를 구하기 위해선 시험감독관이 관리하는 인원으로 학생을 나누면 된다 문제 풀이 // 풀이: 각 시험장 마다 시험감독관의 인원수를 나누어 떠어지 때오 아닐 때를 가려 감독관 수를 더한다 주의 개념 소스코드 # 주의: 파이썬은 범위에 따른 자료형 크..
[백준 13458 c++] 시험 감독 문제 링크 www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제 접근 // 접근: 총감독관은 각 시험관 마다 1명씩 존재한다. // 접근: 시험 감독의 최소 수를 구하기 위해선 시험감독관이 관리하는 인원으로 학생을 나누면 된다 문제 풀이 // 풀이: 각 시험장 마다 시험감독관의 인원수를 나누어 떠어지 때오 아닐 때를 가려 감독관 수를 더한다 주의 // 주의: 총 시험자수는 100만 * 100만 이어서 ..
[백준 2875 python파이썬] 대회 or 인턴 문제 링크 www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 문제 접근 // 접근: 팀의 최대개수 -> 여 2명 남 1명씩 빼야 한팀 문제 풀이 // 풀이: 여 2두명 남 1명 씩 빼는데 인턴쉽 인원보다 커야하고, 각각 빼는 인원보다 많아야 한다 주의 개념 // 개념: 내림차순 정렬 sort(v.begin(), v.end(),greater()); 소스코드 n,m,k = map(int, input().split()) team=0 while True: ifn-2+ m-1>=k andn-2>=0 andm-1>=0: n-=2 m-=1 ..
[백준 2875 c++] 대회 or 인턴 문제 링크 www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 문제 접근 // 접근: 팀의 최대개수 -> 여 2명 남 1명씩 빼야 한팀 문제 풀이 // 풀이: 여 2두명 남 1명 씩 빼는데 인턴쉽 인원보다 커야하고, 각각 빼는 인원보다 많아야 한다 주의 개념 // 개념: 내림차순 정렬 sort(v.begin(), v.end(),greater()); 소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include // c 문법 헤더파일 #include // c++ 문자열 클래스 #include //..
[백준 2217 python파이썬] 로프 문제 링크 www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 접근 // 접근: 여러 줄들의 최대중량 -> 그리디 // 최대중량은 = 선탣된 로프중 최소중량의 로프 * 로프의 개수 문제 풀이 주의 개념 lst.sort(reverse = True) 소스코드 n = int(input()) lst = [int(input()) for_ in range(n)] # 줄바꾸면서 여러개 입력 lst.sort(reverse = True) Max=0 fori in ..
[백준 2217 c++] 로프 문제 링크 www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 접근 // 접근: 여러 줄들의 최대중량 -> 그리디 // 최대중량은 = 선탣된 로프중 최소중량의 로프 * 로프의 개수 문제 풀이 // 풀이: 벡터에 저장 후 오름차순으로 정렬 후 최대중량이 제일 큰 값을 출력 주의 개념 // 개념: 내림차순 정렬 sort(v.begin(), v.end(),greater()); 소스코드 #define _CRT_SECURE_NO_WARNINGS #inclu..
[백준 11399 Python파이썬] ATM 문제 링크 www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 접근 // 접근: 걸리는 시간의 최소합 -> 그리디 // 최소합이 되려면 앞의 사람의 시간일 수록 중복되는 횟수가 많아지니깐 앞에있는 사람일 수록 최소시간이어야 한다 문제 풀이 // 풀이: 벡터로 저장 후 정렬 후 최소합 구한다. 주의 개념 n = int(input()) lst =[int(input()) for _ in range(n)] #줄바꾸면서 여러개 입력 왜 안돼? n = int(input()) lst = list(m..
[백준 11399 c++] ATM 문제 링크 www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 접근 // 접근: 걸리는 시간의 최소합 -> 그리디 // 최소합이 되려면 앞의 사람의 시간일 수록 중복되는 횟수가 많아지니깐 앞에있는 사람일 수록 최소시간이어야 한다 문제 풀이 // 풀이: 벡터로 저장 후 정렬 후 최소합 구한다. 주의 개념 소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include // c 문법 헤더파일 #include // c++ 문자열 클래스 #include // ..
반응형

티스토리툴바