https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 이분탐색 문제이다. 세 수를 선정할 때에, O(N^3) 브루트포싱으로 접근하면 시간초과를 받게 되므로 세 숫자 중 하나는 이분탐색을 통해서 골라내야 한다. O(N^2) 로 두개의 쌍을 더해서 그 합 SUM 을 만들어 주고, SUM의 음수와 가장 가까운 수를 이분탐색으로 구해준 다음 셋의 합이 0에 가까워지도록 갱신해나가면 된다. 이때, lower_bound로 구한 인덱스가 k..

우선순위 큐 문제 매워요 ㅠㅠ 일단 당장 보고 생각난건 우선순위 큐와 위상정렬이다. 근데 다시 :thinking: 과정을 한번 거쳐보고 위상정렬처럼 얘가 정확히 여기 들어간다는 보장이 없어서 우선순위큐로 풀었다. struct people에는 계산시간, 회원번호, 계산대번호 세가지를 저장하고 cmp_pq는 pq를 정렬하기 위한 비교함수, cmp_v 는 벡터를 정렬하기위한 비교함수이다. pq에다 카트를 넣음으로써 계산대가 다 찬 뒤 다음으로 나올 카트를 고를때 pq.top()으로 꺼낼 수 있게 했고, 계산을 마칠때 나오는 순서가 우선 시간순, 시간이 같을때는 안내되는 순서 = 계산대번호가 작은순으로 pq에 넣어서 뽑아주고, pq에 계산대의 갯수만큼의 사람이 들어간 경우 모두 계산중인 상황이므로 pq에서 한명..

정올문제의 연속. 일단 디피를 짜는것까지는 좀 빨라진거같아 다행이다. 괄호 문자열은 더하거나 아니면 감싸주는 방식으로 만들 수 있는데, 이는 디피의 특성인 작은 정답이 모여 큰 정답을 만들 수 있다는것과 같다. 문자열을 K로 두고 string dp[i]를 val(K) = i인 문자열 중 dmap(K)의 최소값을 저장한다. 여기서 dmap(K)가 롱롱인트범위를 벗어날 수도 있을거같다는 생각에 혹시몰라서 문자열형으로 만들어줬고, 그렇기때문에 문자열 두개를 비교하는 string cmp함수를 만들었다 문자열을 숫자로 볼때 더 작은 값을 가지는 문자열을 반환해준다. string convert(string s)는 dp배열에서 저장하는 값이 dmap()일때, 이 dmap()의 반환값 형식으로 저장된 값을 다시 괄호 ..

예선 1번. 이게 난 2번보다 빡셌던거같은데...? 바구니에 나눠 담지 못하는 경우는 차이가 전부 1임에도 불구하고 공이 부족한 경우이다. 즉 계단모양으로 배열하면 되고, 공의 갯수가 계단모양의 넓이보다 작으면 -1을 출력해주면 된다. 이제 계단모양으로 일단 공을 배열해놓고, 계단의 가장 윗층부터 공을 올려놓으면서 한계단씩 내려오는게 공의 개수차이를 가장 작게 하는 배치 방법이다. 그대로 구현만 해주면 AC. 더보기 #include int arr[1234] = {0}; int main(){ int n,k; scanf("%d %d", &n, &k); if(n < k*(k+1)/2){ printf("-1"); return 0; } for(int i=1; i

처음 보고 뇌절왔었던 문제 ㄹㅇ 고등부 넘모 어려워요 ㅠㅠ www.acmicpc.net/problem/20192 20192번: 순서 섞기 정수가 저장된 크기 N인 배열 A가 있을 때, ‘순서 섞기’ 연산은 아래와 같이 정의된다. 크기가 N인 배열 B를 이용하여, 배열 A의 좌측 끝 또는 우측 끝에 있는 값 중 하나를 차례로 꺼내어 배열 B www.acmicpc.net 처음에는 걍 그리디 + 구현인줄알았다 ( 정올 준비용으로 티어 끄고 풀어서 ) 그래서 간단히 짜고 제출했더니 아니나다를까 TLE. 생각해보니 본선 2번인데 구현으로 풀릴리가 없지 어케풀지 한참 고민하고 있는데 뭔가 정렬 비슷하단 생각이 들어서 정렬관련한것들을 인터넷에서 좀 뒤져봤다. 머지소트가 ↗↗의 형태로 주어진 입력을 합쳐 ↗ 하나로 만..