Doby's Lab

https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 해석만 잘 되면 쉬운 문제였다. 이분 탐색이 필요했던 이유는 k의 범위가 1~10^9까지 가질 수 있었기 때문에 O(N)으로 하면 시간 초과가 나서 이분 탐색인 O(logN)으로 풀어야 한다. #include #include using namespace std; int n, k, m; vector v; int main(){ cin >> n >> k >> ..

https://www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net N번 부대에 필요한 사람 수만큼 사람을 1번부터 차례대로 집어넣는다. 어떠한 X번 군번이 주어졌을 때 이 사람은 어느 부대를 들어가야 하는지 알아내야 하는 문제다. 1번 부대부터 필요한 사람 수들을 더하면서 만족하는 범위 안에 들어가면 답을 도출할 수 있다. 하지만, 쿼리는 M개 부대의 수는 N개로 O(N * M) >> O(N * M), 500,000 * 10,000이 되어 시간 초..

https://www.acmicpc.net/problem/1166 1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 이번 문제는 간단히 이분 탐색이라기보다 부가적인 요소로 신경 써야 할 것이 많은 문제였다. 자료형 while을 이용한 이분 탐색이 아닌 for문을 이용해야 함 (혹은 double이 아닌 long double로 선언) 출력은 실수형 솔루션 (+참고 https://vision-ary.tistory.com/2) 1) 자료형 l, w, h가 주어졌을 때 최댓값이 1e27이 되어 long long을 ..

https://www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 이번 문제는 수학 카테고리에 넣고 싶었으나 그래도 문제의 베이스는 이분 탐색이라서 이 카테고리에 넣어둔다. 점프를 최대로 하려면 1칸 점프를 한 뒤, +1 점프, +1 점프로 목적지에 도달해야 최댓값이 도출될 수 있다. 하지만, 100칸이 있을 때는 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14까지 더하면 100이 넘는다. 그래서 이럴 경우에는 13번째 점프를 할 때, 100을 채우게끔 22칸을 뛰어주면 된다. 즉, 코드로 구현을 할 때는 val..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 이분 탐색이라는 문제를 알고서 풀었기 때문에 어느 타이밍에 이분 탐색이 나와야 할지 감을 잡지 못했다. 첫 번째로 떠오른 방법은 1) 입력을 받을 때, 종유석과 석순으로 나누어서 석순이면 밑에서부터 장애물이 하나씩 추가되는 것이기 때문에 1 ~ 입력값까지 +1을 해주고, 종유석이면 위에서부터 밑으로 +1을 해주었다. 2) 각 구간 별로 부숴야 할 장애물들이 저장되어있기 때문에 정렬을 하고, 맨 앞에 ..

평범한 이분 탐색 문제이지만 이번 문제에서 중요했던 포인트가 평소에 내 취약점이라 정리를 해두고 싶었다. 난 기본적으로 범위? 같은 것에 약하다. 혹은 0으로 시작하는지 1로 시작하는지 이런 문제처럼 범위에 영향을 주는 그런 문제들에 좀 약하다. 내가 짰던 코드의 오류 이유 우선 코드를 짜서 TC는 통과할 수 있지만 제출했을 때는 시간 초과를 유발한다. 그리고, 반례도 있었다. 반례의 이유부터 먼저 말하자면 나는 코드를 짤 때, 구간이 아닌 점들로 가로등이 빛을 비추고 있는지 체크했었다. 그러다 보니 4와 5에 빛을 비춘다고 한들 4~5 사이의 구간은 비추지 못하는 것을 알 수 있다. (코드 블록에 그에 따른 반례도 적어두었다.) 시간 초과가 날 거라고는 어느 정도 예상을 했었다. 그래도 구현을 시켜보자..

이번 문제는 이분 탐색이라는 전제가 없었다면 풀 수 없었을 것이다. 이분 탐색이라는 전제가 있어도 논리에 접근하기 까다로운 문제였다. 걸리는 시간을 여러 값으로 추정하며 이분 탐색으로 도달하는 문제다. 논리에 접근했던 방법 처음엔 최소 시간이 걸리는 검색대에 사람들이 몰리게 해야겠다는 생각이 들었다. >> 검색대의 시간들을 배열에 담아 정렬시켰다. 그래서 걸리는 시간(mid)이 주어지면 그 시간 안에 최소 시간 검색대에 몇 명의 사람이 올 수 있는지 카운트해주었다. >> sum을 선언하고 sum이 mid가 될 때까지 걸리는 시간을 더해준 후에 mid가 되면 다음 시간 검색대에서 같은 과정을 반복해주었다. for (int i = 0; i < times.size(); i++) { ll sum = 0; whi..

이 문제를 보았을 때, 너무 쉬운 문제인데 CLASS 2에 왜 있을까라는 생각을 했다. 어떤 수 N이 있다고 가정하자. 'N이 카드 패에 있는지 없는지는 그냥 for문 돌려서 확인하면 끝나는 거 아닐까?'라고 생각할 수 있었다. 하지만, 문제에서의 N과 M의 주어진 범위를 보고, 시간제한을 보면 떠올랐던 생각으로 풀었을 때 '시간 초과'라는 오류를 초래할 수 있다. 왜냐하면 N의 범위가 1~500,000 M의 범위가 1~500,000이면 for문을 돌렸을 때 시간 복잡도가 O(N*M) 일 것이고, 최댓값이 250,000,000,000 즉, 2500억을 넘어가기 때문이다. 시간제한은 1초로 약 1억번 안에 끝내라는 암묵적인 조건을 주기 때문에 for문으로는 처리할 수가 없었다. 해결법 어떠한 배열 안에 특..