Mathematics

[백준] 28297. 차량 모듈 제작 - C++

[UCPC 2023 예선 C번] [Gold I] https://www.acmicpc.net/problem/28297 28297번: 차량 모듈 제작 현대모비스는 한국 외에도 유럽, 중국, 미국, 인도 등 여러 곳에 연구소를 두고 자율주행, 전동화, 커넥티비티 등의 미래기술은 물론 기존 기계 부품(제동, 조향, 현가, 안전, 램프 등)에도 ICT 기 www.acmicpc.net 풀이 수학적 지식과, MST(Minimum Spanning Tree)를 이용해 풀 수 있었던 문제. 대회 당일에는, 시간을 얼마 안 남겨놓고 풀이를 시작해서, 조급하게 Union-Find로 접근하다 O(N^3)으로 TLE를 냈는데, 끝나고 다시 보니 MST로 풀이하면 된다는 것을 깨달았다...! 우선, 두 점 사이의 유클리드 거리는 ..

[백준] 28257. 알록달록 초콜릿 만들기 - C++

[Gold III] https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 백준 제 2회 초콜릿컵 C번 문제 대회 당일 런타임 에러로 애를 먹었던 문제다. 이분탐색할 때 vector를 사용했었는데, 큰 숫자 범위 때문에 메모리 제한을 벗어난 듯 했음. 풀이 조금의 규칙성(?)과, 이분 탐색을 이용해야 하는 문제. 우선, 첫 번째 규칙은, 각 줄에 존재하는 민트초코의 개수. 1개 0개 1개 / 2개 1개 2개 / 3개 2..