우선순위 큐 문제 매워요 ㅠㅠ 일단 당장 보고 생각난건 우선순위 큐와 위상정렬이다. 근데 다시 :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번인데 구현으로 풀릴리가 없지 어케풀지 한참 고민하고 있는데 뭔가 정렬 비슷하단 생각이 들어서 정렬관련한것들을 인터넷에서 좀 뒤져봤다. 머지소트가 ↗↗의 형태로 주어진 입력을 합쳐 ↗ 하나로 만..

한국정보올림피아드 곧응부 문제를 하나씩 풀기 시작해보고 있습니다. 그래도 고등부 상은 있어야지 ㅠㅠ 1번치고 상당히 어려웠던 문제지만 적당히 풀어내는데 성공했습니다. www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net 서브태스크의 조건은 위와 같습니다. 문제를 딱 보자마자 떠오른 풀이는 O(NM)의 풀이로, 이 풀이를 사용하면 42점을 긁어낼 수 있습니다. ( N = S.length()-1, M = T.length()-1 입니다. ) S와 T를 입력 받은 다..

blog.koderpark.dev/145 백준 BOJ 3033 & 1605 - 가장 긴 문자열 & 반복 부분문자열 둘이 동일한 문제라 이것도 깔끔하게 날먹했다. 이 문제는 Suffix Array와 LCP를 구현하는 문제이다 LCP의 최댓값이 바로 문제에서 원하는 정답. www.acmicpc.net/problem/3033 3033번: 가장 긴 문자열 첫째 줄 blog.koderpark.dev 와 97%쯤 동일한 문제 저기서는 LCP의 최댓값을 요구하고 있고, 이 문제는 LCP와 Suffix Array를 동시에 출력해주면 된다. www.acmicpc.net/problem/9248 9248번: Suffix Array Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들..