https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 그리디 문제다. 화물의 무게와 크레인의 무게를 정렬한 후 무게 제한이 큰 크레인부터 화물을 담았다. 벡터를 이용했고, 크레인에 화물을 담을 때, 화물을 벡터에서 제거했다. #include #include #include using namespace std; int limit[50]; vector box; int main() { // 입출력 속도를 단축시키기 위함 ios::sync_..
분류 전체보기
https://www.acmicpc.net/problem/1082 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net DP와 그리디 문제라고는 하는데 큰 수 연산이 필요할 것 같아 DP를 사용하지 않았다. 그리디 같은 구현 같은 그런,,, 방 번호가 크기 위해서는 자리수가 많은 게 제일 중요하다고 생각했고, 그 후 숫자가 큰 게 중요하다 생각했다. 숫자를 가격 기준으로 오름차순 정렬 후 가장 싼 값으로 배열을 채웠다. 나누기 연산을 이용했고 몫만큼 배열을 채운 후, 나머지만큼 큰 숫자로 바꿨다. 배열의 결과값이 모두 0인 경우 예외처리를 했다. 0이 하나인 경우 0 출력한다. 0이 2..
https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net DP와 완전 탐색 문제다. DP의 배열을 3차원으로 생성했다. dp[원하는 문을 연 횟수][열린 문 중 왼쪽][열린 문 중 오른쪽] 특정 시점에서 최선의 선택이 다음 선택에서는 최선이 아닐 수도 있기 때문에 완전 탐색을 이용했다. 최대 문의 수가 20이라는 점에서 완전 탐색을 이용해도 시간 초과가 나지 않을 것이라 판단했다. #include #include using namespace std;..
https://www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d ≤ 10,000이고, 1 ≤ N ≤ 1,000,000이다. www.acmicpc.net DP와 누적 합 문제다. #include using namespace std; long long dp[1000001]; int main() { // 입출력 속도를 단축시키기 위함 ios::sync_with_stdio(0); cin.tie(0); int a, b, d, N;cin >> a >> b >> d >> N; for (int i = 0; i < a; i++) dp[i] = 1; for (int i = a; i = ..
https://www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 우선순위 큐와 구현 문제다. 우선순위 큐에 입력 받은 값을 넣어 오름차순으로 정렬되게끔 했다. 2차원 배열을 이용해서 컴퓨터 사용이 끝나는 시간과 몇 명이 이용했는지 저장했다. 반복문으로 컴퓨터를 사용하지 않았거나, 사용 기록이 있으나 이미 퇴실한 자리를 찾아 저장했다. #include #include using..
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선수위 큐와 그리디 문제다. 처음에는 작은 수가 여러 번 더해지는 게 최솟값이 나올 거라고 생각해 정렬 후 각 수에 n - i를 곱해서 더하는 방법을 생각했다. 이 방법은 항상 앞의 두 수 합에 바로 뒤에 숫자를 더한다. 반례가 있을 것 같다는 생각이 들었다. (a + b) (c + d) e 를 더하는 것이 최솟값이 나오는 경우가 있을 것 같았다. 있었다. 원소 삽입마다 정렬이 되..
