특이한 풀이가 있어 쉬운 난이도인 실버 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번인데 구현으로 풀릴리가 없지 어케풀지 한참 고민하고 있는데 뭔가 정렬 비슷하단 생각이 들어서 정렬관련한것들을 인터넷에서 좀 뒤져봤다. 머지소트가 ↗↗의 형태로 주어진 입력을 합쳐 ↗ 하나로 만..