BOJ 백준 13257 생태학 문제: https://www.acmicpc.net/problem/13257 13257번: 생태학 첫째 줄에 N, C, D, M이 주어진다. (1 ≤ N ≤ 20, 1 ≤ C ≤ 20, 1 ≤ D ≤ 5, 0 ≤ M ≤ N) www.acmicpc.net $D$일 동안 매일마다 $C$ 마리를 포획하여 측정기가 부착이 안 된 새에 모두 측정기를 부착한다고 한다. 새가 총 $N$ 마리일 때, $D$일 후 $M$ 마리가 될 확률을 구하는 것이 문제이다. 처음에 문제를 봤을 때는 $N$, $C$, $D$, $M$의 크기가 작은 편이어서 브루스포스로 구하는 단순 확률 문제인 줄 알았으나, 날마다 C마리의 새를 포획했을 때 몇 마리가 이미 측정기가 부착되었는지를 고려해야 하므로 생각보다 ..

BOJ 백준 23242 Histogram 문제: https://www.acmicpc.net/problem/23242 23242번: Histogram For a range of $[1, n]$, the natural numbers in the interval are called the data values and let $f_i$ be the frequency count of the data value $i$ in the range. The frequency of a data value $i$ is the number of occurrences of the data value $i$ in the lis www.acmicpc.net 길이가 n인 수열을 B개의 bucket으로 나누었을 때, 각 bucket의 ..

BOJ 백준 20047 동전 옮기기 문제: https://www.acmicpc.net/problem/20047 20047번: 동전 옮기기 입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T www.acmicpc.net 두 개의 동전을 서로 순서를 바꾸지 않고 자리를 이동하여 문제에서 주어지는 동전 배치를 만들 수 있는지 묻는 문제이다. 학회에서 ACM ICPC 예선을 준비하면서 팀원과 같이 풀었던 문제이다. 처음에는 Queue를 이용하여 푸는 구현 문제인 줄 알고 시도했는데, 계속 채점을 돌려봐도 86퍼센트에서 틀렸다고 떠서 접근 자체가 틀..

BOJ 백준 16467 병아리의 변신은 무죄 문제: https://www.acmicpc.net/problem/16467 16467번: 병아리의 변신은 무죄 학교공부를 끝내고 집을 가던 다진이는 길가에서 병아리를 팔고 있는 아저씨를 발견했다. 병아리를 무척 사고 싶었던 다진이는 병아리의 상태를 확인하지도 않고 한 마리를 사서 집으로 향했다 www.acmicpc.net 병아리가 매일마다 혼자서 알을 한 개씩 낳고 이 알은 K일 후에 부화할 때, N일이 지난 후의 병아리 수를 구하는 것이 문제이다. 개인적으로 이런 유형의 문제는 우선 관찰을 자세히 하는 것이 중요하다고 생각한다. K = 0일 때와 K = 1일 때를 한 번 살펴봤다. K = 0일 때는 i일 후의 병아리의 수를 2의 거듭제곱 꼴로 나타낼 수 있고..

BOJ 백준 22953 도도의 음식 준비 문제: https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net K개의 요리를 조리하는 N명의 요리사의 조리시간이 주어진다. 한 요리사에게 격려를 여러 번 할 수 있고, 요리사에게 격려를 한 번 할 때마다 격려를 받은 요리사의 조리 시간은 1초 감소한다. 격려할 수 있는 최대 횟수가 C회일 때, K개의 요리를 조리하는 데..

BOJ 백준 22991 수요응답형 버스 문제: https://www.acmicpc.net/problem/22991 22991번: 수요응답형 버스 현대오토에버는 In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라 관련 업무를 수행하는 회사이다. 현재 현대오토에버에서 수요응답형 버스(MOD)를 개발하고 있다. 수요응답형 버스는 승객이 호 www.acmicpc.net 배차 요청이 N개, 버스가 M개 주어졌을 때, 조건을 만족하면서 배차 요청에 버스를 최대 몇 대 배차 가능한지를 구하는 문제이다. 버스를 요청에 배차 가능한 조건은 다음과 같다. 배차의 탑승 인원 ≤ 버스의 정원 배차의 최대 대기 가능 시간 ≥ 버스의 도착 예정 시간 올해 2021년 SUAPC Summer(https://icpc-sinc..

BOJ 백준 22954 그래프 트리 분할 문제: https://www.acmicpc.net/problem/22954 22954번: 그래프 트리 분할 첫 번째 줄에 정점의 개수 $N$, 간선의 개수$M$이 주어진다. ($1 \le N \le 100\,000$, $0 \le M \le 200\,000$) 두 번째 줄부터 $M$줄에 걸쳐서 간선을 나타내는 정수 $u$와 $v$가 주어진다. ($1 \le u, v \le N$, $u www.acmicpc.net 정점 N개, 간선 M개의 그래프가 주어졌을 때 서로 다른 크기의 2개의 트리로 분할하라는 문제이다. 문제에서 주어지는 그래프에는 특별한 제약 사항이 없으므로 이미 그래프가 여러 개의 연결 요소로 분할되어 있을 수도 있다. 그래서 그래프의 연결 요소 개수를..

BOJ 백준 10273 고대 동굴 탐사 문제: https://www.acmicpc.net/problem/10273 10273번: 고대 동굴 탐사 입력의 첫 줄엔 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 10) 각 테스트 케이스의 첫 줄엔 탐사할 수 있는 동굴의 수 N과 서로 직접 연결된 동굴 쌍의 수 E가 주어진다. (1 ≤ N ≤ 2 · 10 4; 0 ≤ E www.acmicpc.net 문제 내용이 길고 복잡해서 처음에는 문제 풀기가 까다로웠다. 그런데 간단히 정리하면 다음과 같다. 단방향 그래프가 주어지고 각 정점 방문 시 얻을 수 있는 이익과 각 간선을 탔을 때의 비용이 주어졌을 때, 해당 그래프를 탐색해서 얻을 수 있는 순이익의 최댓값을 구한다. 앞의 작업 진척도에 관한 내용은 사실 크..