중학교때 잠깐 봤었던거 같은 문제 [원석방 산하 폐수방] 1일차 셋 div 2 A번이다. https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 일단 간단한 그림을 그려보든지 해서 알수 있는 정보는 벽장문을 옮길때, 횟수는 그냥 A번 벽장을 B번 벽장으로 옮기고자할때 abs(A-B) 이다. 사이에 C번벽장이 있더라도 이는 동일하다. 여기서 좀 이상한 사고를 거쳐서, 브루트포싱하자는 의견에 도달했다. 벽장 두개가 기본적으로 주어져있고, 열려있는 벽장..

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

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