groti's blog

1. 문제 해석 https://www.acmicpc.net/problem/3671 3671번: 산업 스파이의 편지 문제 안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요. 저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매우 유능한 산업 스파이이기 때문에, 연구 결과를 어렵지 않게 얻을 수 있었습니다. 하지만, 제가 올 것을 미리 알았는지 연구소에서는 연구 결과를 모두 서류 절단기에 넣어버렸습니다. 어쩔수 없이 저는 눈물을 머금고 종이 조각을 모두 훔쳐왔습니다. 저를 고용한 사람은 매우 무 www.acmicpc.net 최소 1개, 최대 7개의 숫자가 주어진다. 숫자를 적절하게 배치하여 만들 수 있는 소수의 개수를 구해야 한다...

1. 문제 해석 https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. (1 ≤ L ≤ 109, L은 정수) www.acmicpc.net N개의 김밥이 있다. 김밥의 양끝은 Kcm 잘라낸다. 김밥의 길이가 2 * Kcm보다 짧을 경우 한쪽만 자고, Kcm 이하면 버린다. 손질된 김밥을 Pcm 크기로 일정하게 자르려고 할 때, M개 이상의 김밥 조각을 얻을 수 있도록 하는 P의 최대값을 구해야 한다. 2. 접근방법 1부터 가장 긴 깁밥의 ..

1. 문제 해석 https://www.acmicpc.net/problem/18114 18114번: 블랙 프라이데이 첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ 108, N과 C는 양의 정수) 다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진다. (1 ≤ w ≤ 108, w는 양의 정수) www.acmicpc.net N개의 물건이 있다. 물건의 무게는 모두 다르다. 최대 3개의 물건을 선택하여 무게 C를 맞출 수 있는 조합이 가능한 지 판단해야 하다. 물건의 중복 선택은 불가능하다. (1 M; for (int i = 0; i > arr[i]; chk[arr[i]] = true; }..

1. 문제 해석 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 문제를 읽고 재귀로 완전탐색하면 되겠다 싶었는데 N 제한이 30 인 것을 보고 고민에 빠졌다. 모든 경우를 확인할 때 최대 2^30번을 확인해야 하기 때문이다. 그래서 알아본 Meet in the Middle 알고리즘을 적용하면 수행시간을 크게 줄일 수 있다. (개념 참고: Meet in the Middle) 최대 C만큼의 무게를 담을 수 있는 가방이 있다. N개의 물건이 있..