웰제오의 개발 블로그

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 접근법 및 풀이 이제 입력크기를 통해 시간초과를 따지는 과정이 자연스럽게 이루어지는 것 같다 v 완전탐색은 당연히 시간초과가 날 것 이고, 최적화를 진행한다면 dp 인가 싶기도 했지만, 문제의 조건 때문에 모든 케이스에 대해서 상위 문제가 하위 문제를 포함하지 못하므로 dp 도 아니었다. 회의실을 고르는 작업이 시간순서에 따라 제약을 받으므로, 우선 정렬을 수행해야할 것 같은 느낌이 들었고, 이내 예전에 비슷한 문제를 학교수업 때 들은 기억이 났고, 정렬을 통한 그리디 문제였음이 떠올랐다 그리디 하게 회의실을 선..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 접근법 주어진 랜선들에 대해, 이 랜선들에서 동일한 L 이란 길이만큼의 랜선들을 잘라내어, 그 총 합이 N 을 만족하는지 확인하면 되는, 조건 자체는 간단한 문제이다 다만 랜선 최대의 길이가 2^31 - 1 점을 미루어 보아 브루트포스는 시간 초과가 난다 탐색 하는데 있어서 발생하는 시간을 줄이는건 이분탐색, 그 중에서도 대표적인 파라매틱 서치 문제의 유형이다 풀이 및..

https://www.acmicpc.net/problem/23560 23560번: 약 백준이는 $N$일 동안 약을 먹어야 한다. 약은 아침, 점심, 저녁에 한 번씩 먹어야 하고, 한 번 먹는 약은 약 봉투에 담겨있다. 약 봉투는 $3N$개가 일렬로 붙어 있고, {(아침 약), (점심 약), (저녁 약)} www.acmicpc.net 접근법 나는 아직 ps 내공이 부족해서 그런지 문제를 딱 보고 이런 유형이겠다 싶은게 떠오르지가 않는다 늘 그렇듯 브루트 포스, 완전탐색 수행 이후 해당 풀이에서 최적화를 진행하는 식으로 문제를 접근했다 배열 arr 를 자연수 1 ~ N 까지 오름차순으로 채운 뒤, 약을 구분하기 위해서 원소를 2로 나눈 나머지를 통해 아침, 점심, 저녁 약을 구분했다 완전 탐색을 수행할 경우..