반갑습니다!

1939번: 중량제한 www.acmicpc.net 풀이 시간 초과와 메모리 초과가 발생하기 쉬운 문제이다. 결론부터 얘기하면 DFS + 이분탐색 또는 BFS + 이분탐색으로 해결할 수 있다. 문제를 읽어보면 그래프 탐색 문제이므로 DFS / BFS를 사용해야하는 것은 쉽게 알 수 있다. 그런데 문제에서 C가 최대 1,000,000,000이 되기 때문에 물품의 최대값을 찾을 때 선형 탐색으로는 찾을 수 없다는 것을 알 수 있다. 따라서 Parametric Search (이분 탐색)을 사용해 가능한 물품의 무게를 찾아서 시간 초과를 방지할 수 있다. 그리고 N의 최댓값이 10,000이므로 인접 행렬을 사용하면 메모리 초과가 발생한다. 따라서 인접 리스트를 통해 메모리 초과를 방지해서 해결했다. 코드 C++ ..

6236번: 용돈 관리 www.acmicpc.net 풀이 이분 탐색으로 해결할 수 있는 문제이다. K금액을 기준으로 이분 탐색을 진행하면 된다. 이 때 left는 1원부터 인출 가능하므로 1, right는 전체 금액을 한번에 인출할 수 있기 때문에 전체 금액이 된다. 코드 #include #include using namespace std; int n, m; int money[100001]; bool is_possible(int mid) { int cnt = 1; int sum = mid; for (int i = 0; i < n; i++) { // 돈을 인출해도 그 날 사용 금액보다 적으면 false if (mid < money[i]) return false; // 남은 돈이 그 날 사용 금액보다 적은 ..

3079번: 입국심사 www.acmicpc.net 풀이 [프로그래머스] 입국심사와 동일한 문제이다. 코드 #include #include #include using namespace std; int n, m; int t[100001]; long long binary_search() { long long ans = numeric_limits::max(); long long left = 1; long long right = (long long)(*max_element(t, t + n)) * (long long)m; while (left > n >> m; for (int i = 0; i > t[i]; cout

2343번: 기타 레슨 www.acmicpc.net 풀이 이분 탐색을 통해 해결할 수 있는 문제이다. 블루레이의 용량을 기준으로 이분 탐색을 진행하면 된다. 초기 left, right 값을 설정하는 것이 중요하다. 모든 레슨이 1개의 블루레이에 담길 수 있기 때문에 right값은 모든 레슨의 길이의 합이 되고, 하나의 레슨을 여러 블루레이에 남아 담을 수 없기 때문에 left 값은 가장 긴 레슨의 길이가 된다. 코드 #include #include using namespace std; int n, m; int l[100001]; int binary_search(int r) { int ans = 987654321; int left = *max_element(l, l + n); int right = r; w..

12015번: 가장 긴 증가하는 부분 수열 2 www.acmicpc.net 풀이 LIS 알고리즘 문제이다. 일반적으로 LIS 문제는 동적계획법으로 풀 수 있는 전형적인 문제이지만, 이 문제에서는 N의 최댓값이 1,000,000이므로 다른 방법으로 해결해야한다. 아래의 코드는 이진 탐색을 이용한 LIS 알고리즘이다. C++ STL에 구현되어있는 lower_bound()를 이용해서 해결했다. 코드 #include #include using namespace std; int n; int a[1000001]; vector lis; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; i..