백준 1253 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 전 나의 생각 N개의 수에서 어떤 수가 다룬 수 두 개의 합으로 나타낼 수 있다면 "좋다" 라고 한다. 따라서 "좋다"를 만족하는 좋은 수가 몇 개인지 구해야한다. 조건 N(1 ≤ N ≤ 2,000) |Ai| ≤ 1,000,000,000, Ai는 정수 Solution 조건으로 알 수 있는 것은 일반적인 탐색 방법인 3중 for문을 이용한 방법은 2000 * 2000 * 2000의 계산 횟수로 시간 제한을 ..
알고리즘 및 자료구조/이분탐색
백준 3151 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 풀이 전 나의 생각 팀원의 코딩 실력 N개가 주어지는데 이 중 3개의 실력을 골라서 0이 될 수 있는 경우의 수를 모두 구해야한다. 조건 1 ≤ N ≤ 10000 -10000 ≤ Ai ≤ 10000 Solution 조건을 보면 N은 최대 10000개 까지 주어질 수 있다. 일반적인 풀이법으로 생각해보면 요소 두개를 더해야 하니 2중 for문을 사용해야하고 더한 요소가 실제로 0을 만들 수..
백준 2295 https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 전 나의 생각 N개의 자연수로 이루어진 집합 U에서 3개의 선택된 수의 합이 집합 U에 포함되어 있어야 하며 최대의 수가 되는 값을 구해야한다. 조건으로 알 수 있는 것들 - N(5 자연수는 int형으로 설정한다. - x, y, z, k가 서로 같아도 된다. -> x, y, z, k가 중복될 수있다. Solution 아무리 N이 ..
백준 14921 https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 풀이 전 나의 생각 얼마전에 풀었던 용액 문제와 똑같은 유형이다. https://tjdgh7419.tistory.com/151 [알고리즘] C++ 백준 2467 용액 백준 2467 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다...
백준 2467 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 전 나의 생각 N개의 산성 용액과 알칼리성 용액 배열이 주어진다. 산성 용액 + 알칼리성 용액, 산성 용액 + 산성 용액, 알칼리성 용액 + 알칼리성 용액 중 0에 가장 가까운 값을 찾아야한다. N은 2이상 10만이하의 정수, 용액은 -10억 이상 10억 이하이다.(시간 제한 1초) 여기서 바로 해결할 수 있는 방법은 이중 for문을 돌며 하나 씩 탐색하며 계산을 해주는 ..
백준 18869 https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 풀이 전 나의 생각 M개의 우주가 주어지고 각 우주는 1부터 N까지 번호가 매겨진 행성 N개가 있다. 두 우주 A와 B에 있는 행성들이 아래의 조건을 만족한다면 균등한 우주라고 부른다. 조건 Ai Aj → Bi > Bj 우주, 행성, 행성의 크기의 범위 2 ≤ M ≤ 100 3 ≤ N ≤ 10,000 1 ≤..
백준 16401 https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 풀이 전 나의 생각 길이를 가진 N개의 막대 과자가 주어지고 이 막대 과자를 M명의 조카에게 최대한 길게 나눠주려고한다. 단, 막대 과자는 여러 조각으로 나눠질 수 있지만 과자를 하나로 합칠 수는 없다. 예를 들어 3명의 조카와 5, 6, 7, 8, 9의 길이를 가지는 막대 과자 5개가 있다고 가..
백준 1654 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 전 나의 생각 주어진 K개의 랜선들을 어떤 값으로 나눠서 목표 랜선 개수 N개를 만들어야한다. 또한 나눠야 하는 값은 최댓값이어야한다. 일반적으로 생각해보면 1부터 랜선의 최대 길이 만큼 탐색하면서 모든 길이를 나누면 될 것같다. 하지만 랜선의 길이는 2^31 - 1 이기 때문에 약 21억번 만큼 탐색을 진행하며 10000개의 랜선을 나눈다고 가정하..
