특이한 풀이가 있어 쉬운 난이도인 실버 2임에도 불구하고 블로그 글을 써보려 한다. 원래 정해는 이제 최대공약수를 이용하는 풀이법이다. 최대공약수로 i 와 j를 나눠주면, 이 두가지 수가 이제 마치 "기약분수" 처럼 보이게 되고, 이를 통해 중복을 제거해줄수 있다. 하지만 여기서 기약분수라는 저 느낌을 잘 활용하면 소스코드의 길이를 대폭 줄일 수 있다. www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 고등학교 2학년 교육과정에 라디안 각을 배우게 되는데, 이..

간선을 생으로 구현하면 MLE가 나오는 문제 간선의 갯수를 줄이기 위해서는 더미노드를 만들어서 하이퍼 튜브가 문어발 같은 느낌으로 펼쳐지게 설계해주면 된다. 그러면 모든 노드를 최소한의 간선만 가지고( 정점을 하나 더 써서 ) 이어줄 수 있고, 테스트케이스의 정답을 더미노드를 사용해서 문제를 해결하면 1 K 3 K 6 K 9 가 되는데, 정답, 즉 4를 N이라 하면 더미노드 K의 갯수는 N-1개 이다. 따라서 실제 정답은 우리가 bfs를 통해 구해준 가중치를 K로 두었을때 (K+1)/2를 출력해주면 답이 된다. 메모리 아끼는 팁으로는 가중치를 vis배열이랑 같이 묶어서 한번에 저장해줄 수 있다는 정도? 위의 더미노드를 만든다는 생각에만 도달하면 쉽게 AC를 받을 수 있다. 더보기 #include usin..

우선순위 큐 문제 매워요 ㅠㅠ 일단 당장 보고 생각난건 우선순위 큐와 위상정렬이다. 근데 다시 :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가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들..

둘이 동일한 문제라 이것도 깔끔하게 날먹했다. 이 문제는 Suffix Array와 LCP를 구현하는 문제이다 LCP의 최댓값이 바로 문제에서 원하는 정답. www.acmicpc.net/problem/3033 3033번: 가장 긴 문자열 첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다. www.acmicpc.net www.acmicpc.net/problem/1605 1605번: 반복 부분문자열 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열' www.acmicpc.net 배열이 상상히..

마나커/마나허/manacher's 알고리즘을 구현하는 문제이다 똑같은 문제가 두개 있어서 깔끔하게 날먹했다. www.acmicpc.net/problem/14444 14444번: 가장 긴 팰린드롬 부분 문자열 알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net www.acmicpc.net/problem/13275 13275번: 가장 긴 팰린드롬 부분 문자열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다. www.acmicpc.net 마나허 알고리즘이 NYPC예선문제 풀때도 나왔었던거 같은데 그..