알고리즘98 백준 g5 2467 용액 c++ https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 설명 -10^9 ~ 10^9 범위의 특성값을 지닌 용액 N개가 있다. (N 당연히 시간초과 2. binary search로 합이 최대한 0에 가깝게 해보기 하나의 베이스 용액을 정하고, (arr[i]) x축을 더할 용액의 특성값, y축을 특성값의 합으로 두었을 때 우상향 그래프 이므로 이분탐색을 쓸 수 있겠다 생각함. while st < en res = arr[i] + arr[mid] .. 2024. 2. 19. 백준 s2 2805 나무 자르기 c++ https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 문제 설명과 풀이는 https://kyj0032.tistory.com/52와 유사하게 parametric search 썼음 조건(잘린 나무 합이 M 이상)에 맞는 절단기 높이 H의 최댓값을 구해야 함. 절단기 높이 H는 최대 10^9으로 1씩 내려가며 완전탐색을 할 수가 없음. 대신 이분탐색으로 높이 H를 탐색하며 조건에 맞는 최적해 찾기 정리하자면, .. 2024. 2. 17. 백준 s2 16401 과자 나눠주기 c++ 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 문제 설명과 풀이는 https://kyj0032.tistory.com/52 참고, 거의 유사함. 다만 랜선 자르기 문제는 불가능한 경우의 수가 없었지만, 이 문제는 0을 출력해야 함. 단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다. 코드 /*boj s2 16401 과자 나눠주기*/ .. 2024. 2. 17. 백준 s4 1822 차집합 c++ https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net /*boj s4 1822 차집합*/ #include #include #include #define MAXN 500010 using namespace std; int N, M; int A[MAXN]; int B[MAXN]; vector ans; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M.. 2024. 2. 17. 백준 s5 10815 숫자 카드 c++ https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 코드 /*boj s5 10815 숫자 카드*/ #include #include #define MAXN 500010 using namespace std; int N, M; int card[MAXN]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = 0; i < N; i++) cin.. 2024. 2. 17. 백준 s2 1654 랜선 자르기 c++ 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개를 만들어야 한다. 이때 자른 랜선의 최대 길이는? 풀이 (https://blog.encrypted.gg/985) Parametric Search 정의) 조건을 만족하는 최소/최댓값 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법 보통은 조건을 이분탐색으로 해서 답을 구하지만, 답의 범위를 이분탐색으로 나누어서.. 2024. 2. 16. 백준 g4 2295 세 수의 합 c++ 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가 있을 때, 각 원소 a, b, c, k를 골랐을 때 a + b + c = k 를 만족하는 최대 k 구하기 집합이므로 각 원소는 중복되지 않으나, a b c 는 서로 같아도 된다. 풀이 1. O(N^3*logN) 풀이 1) 세 원소를 고른다. 1000C3 -> N^3 2) 고른 세 원소의 합이 존재하는지 binar.. 2024. 2. 16. 백준 s2 18870 좌표 압축 c++ https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 문제 X_i` = X_i보다 작은, 중복되지 않은, 다른 원소의 개수 풀이 배열을 두 번씩 돌리면서 각각 X_j의 개수를 세는 방법도 있지만 N O(NlogN) 코드 /*boj s2 18870 좌표 압축*/ #include #include #include #define MAXN 1000010 using namespace std; int N; in.. 2024. 2. 15. 백준 s2 11501 주식 c++ https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 가장 최대로 수익을 얻으려면, 항상 고점에서 팔아야 한다. max값이 나올 때까지 주식을 하나씩 사다가, max값이 나오면 그때 다 판다. 또, 남은 주식들 중 max값이 나올 때까지 주식을 하나씩 사다가 max값이 나오면 그때 다 판다. 처음에는 앞에서부터 팔려고 했으나, 남은 기간 중 max값을 구하기 어려워 뒤에서부터 시작했다. 만약 max값보다 가격이 낮다면, 그 주식을 .. 2024. 1. 26. 이전 1 ··· 3 4 5 6 7 8 9 ··· 11 다음
