하바나바나나

https://www.acmicpc.net/problem/5821 5821번: 쌀 창고 쌀 창고 이 경우에는 창고의 위치에 대한 여러 개의 최적 위치가 있다: 10 이상 14 이하의 어느 정수 위치에든지 쌀 창고를 둘 수 있다. 위의 그림은 최적 위치들 중의 하나를 보여준다. 이 경우 10 www.acmicpc.net 쌀 창고의 위치가 주어지고 쓸 수 있는 비용이 주어질 때 해당 비용 내에서 최대한 많은 쌀을 옮기는 문제입니다. https://www.acmicpc.net/problem/2375 2375번: 농구 골대 세우기 첫 줄에 농구를 좋아하는 마을의 개수인 n이 주어지고 다음 줄부터 xi, yi, pi와 같이 한 줄에 농구를 좋아하는 하나의 마을에 대한 정보가 주어진다. 두 마을의 위치가 같은 경우..

https://www.acmicpc.net/problem/2185 2185번: 직사각형의 합집합 첫째 줄에 직사각형의 개수 N이 주어진다. 다음 N개의 줄에는 각 사각형의 정보를 나타내는 네 정수 x1, y1, x2, y2가 주어진다. 이는 사각형의 대각선으로 마주 보는 두 꼭짓점의 좌표가 (x1, y1), (x2, www.acmicpc.net 풀이 쓰기 귀찮아서 shiftpsh 님에게 대신 써달라고 했습니다. 아래는 shiftpsh 님의 글입니다. 둘레를 구해야 한다는 점에서 생각해 보면 $x$축과 $y$축을 따로 생각해도 된다는 사실을 알 수 있습니다. 지금부터는 $x$축에 수직인 선분들만에 대해 설명해 보겠습니다. 직사각형의 양 끝 선분을 봅시다. 왼쪽 선분을 '선분이 추가되는 이벤트'로, 오른쪽을..

SCPC 2차 예선을 쳤습니다. 잘 친건 아니지만 작년보다는 높은 성적이어서 만족스럽습니다. 계속 조금씩 성적이 오르고 있으니 내년에는 본선에 갈 수도 있지 않을까요? 아님망고... 까먹기 전에 풀이를 간단하게 남겨봅니다. 1. 수열 연산 배열에 연속된 구간에 update 쿼리를 통해 값을 1 증가시킬 수 있고, 배열의 모든 수를 $k$ 이상으로 만드는 update 쿼리의 최소 횟수와 그 때의 최소 비용을 구하는 문제입니다. 이 때 쿼리의 비용은 연속된 구간의 길이입니다. 잘 생각해보면 update 쿼리의 최소 횟수는 $k$ - 배열의 최솟값이라는 것을 알 수 있습니다. 최솟값을 $k$로 만들어주기 위해서는 $k$ - 최솟값 만큼의 update 쿼리가 필요하고 해당 쿼리를 하는 과정에서 나머지 모든 수를..

생일인 분에게 밥을 사주러 시멘트 서울에 갔다왔습니다. 입구가 찾기 되게 어려웠습니다. 역에서 멀기도 해서 엄청 걸었는데, 너무 더워서 힘들었습니다. 빨리 들어가서 먹고 싶었어요. 들어가니 좌석에 안내해주셨습니다. 간단하게 나오는 메뉴에 대해 설명해주고 있습니다. 시멘트 서울은 파스타바인데, 생면을 쓴다고 합니다. 근데 사실 저는 생면이랑 그냥 면이랑 식감 빼고는 잘 구분 못 합니다. 그래도 맛있게 먹고 왔어요. 앉아서 좀 기다리니 나온 아뮤즈 부쉬입니다. 왼쪽은 연어, 오른쪽은 치킨, 아래쪽은 피클이었던 거 같습니다. 셋 다 무난하게 맛있었고 피클이 상큼해서 좋았습니다. 사실 면을 그렇게 좋아하지 않기 때문에, 오늘 먹었던 것들 중에서 제일 만족스러웠습니다. 그리고 얼굴 모양이 귀여워서 좋았어요. 처음..

https://www.acmicpc.net/problem/5502 5502번: 팰린드롬 팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 www.acmicpc.net 딱 보고 아 이거 이차원 dp네 라고 생각했는데 그 이후로 한 이틀간 못 풀었습니다... 은둔고수 님이 저에게 완성된 팰린드롬에서 뺀다고 생각해 보라고 힌트를 주셨는데, 그거 듣고 조금 고민하다가 풀었습니다. $dp(i, j)$는 $i$번째 문자와 $j$번째 문자가 같으면 $dp(i+1,j-1)$이고 다르면 $min(dp(i+1, j), dp(i, j-1)) + 1$이 됩니다. cologne 님이 처음에 원래 문자..

https://www.acmicpc.net/problem/8872 8872번: 빌라봉 첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. N: 빌라봉의 개수 M: 이미 존재하는 길들의 개수 L: 뱀이 새로 지어진 길을 통행하는데 걸리는 시간 (일 단위). A, B, www.acmicpc.net 설명이 조금 길지만 정리해보면 포레스트가 주어질 때, 정점들을 잘 이어 트리로 만들면서 트리의 지름이 가장 작게 하면 됩니다. 트리의 지름을 사용하는 문제를 오랜만에 봐서 새로웠습니다. 이 문제를 풀기 위해서는 그리디한 방법을 사용할 수 있습니다. 임의의 트리 두 개를 이을 때, 각 트리의 지름에 중간에 있는 중점끼리 이어주는 것이 새로 만들어지는 트리의 지름을 ..

https://www.acmicpc.net/problem/5859 5859번: Liars and Truth Tellers After spending so much time around his cows, Farmer John has started to understand their language. Moreover, he notices that among his N cows (2 > n >> m; UF_init(2 * n); int ans = 0; for (int i = 0; i > a >> b >> c; if (c == 'T') { Union(a, b); Union(a + n, b + n); } else { Union(a, b + n); Un..

저녁에 그림 그리면서 수다 떨다가 아 코포 있었지! 하고 급하게 친 코포였는데 평소보다 잘 쳐서 기분이 좋습니다. 아마 레이팅 최고점을 찍을거 같아요. 문제는 잘 풀었는데 실수가 많았던 건 아쉽네요. 더 잘 칠 수 있었을 것 같지만 이 정도도 충분히 만족스럽습니다. 앞으로도 골랜디 열심히 해야지. A. Everyone Loves to Sleep (+) 시간과 분을 전부 분 단위로 바꿔서 계산하면 쉽습니다. 알람 시간이 잠에 든 시간보다 뒤라면 그냥 빼주면 되고 이전이라면 24 * 60을 더한 다음 빼주면 됩니다. 이렇게 구한 값들 중 최솟값을 출력해주면 됩니다. Div.3 A번 치고는 귀찮은 문제가 나온 것 같아서 당황했습니다. 그래서 조금 늦게 푼 것 같습니다. B. Remove Prefix (+) 값..

https://www.acmicpc.net/problem/1635 1635번: 1 또는 -1 첫째 줄에 두 정수 N과 M이 빈 칸을 사이에 두고 주어진다. (2 ≤ N ≤ 100, N은 짝수, 1 ≤ M ≤ 10,000) 이어서 M개의 줄에 걸쳐 수열 a1, a2, ..., aN이 한 줄에 하나씩 주어진다. 각 줄에는 1 또는 -1의 정수 www.acmicpc.net 개인적으로 되게 재밌는 constructive 문제였습니다. 사실 증명은 아직 잘 모르겠습니다... proof by AC 했어요. 총 $N$개의 수열을 쓴다는 아이디어에서 출발했는데, 어떤 점을 기준으로 수열을 왼쪽과 오른쪽을 나눴을 때 왼쪽 구간의 합과 오른쪽 구간의 합이 같으면 한쪽 구간에는 -1을, 반대쪽 구간에는 1을 곱해주는 방식으..

여름 엽서 꾸미기 이벤트가 종료되었습니다. 다들 재밌게 즐기셨나요? 솔브드에서 처음 시도해보는 형태의 이벤트였는데, 지금까지의 모든 이벤트가 그랬지만요 여러 일들을 거친 끝에 그래도 무사히 종료되어서 다행이라고 생각합니다. 이번 이벤트는 지금까지의 이벤트와 다른 점들이 꽤 있었기에, 이벤트의 뒷사정을 살짝 알려드리고자 간단한 회고를 작성해봅니다. 트리 꾸미기 사실 비슷한 형태의 이벤트 기획은 꽤 오래 전부터 있었습니다. 본래 이벤트 초안은 '트리 꾸미기' 였는데, 이름에도 알 수 있듯이 크리스마스 때 기획된 이벤트였습니다. '트리 꾸미기'는 완전 이진 트리가 주어지고 트리의 각 노드에다가 문제를 풀어서 받은 오너먼트를 끼워넣는, 엽서 이벤트와 크게 다르지 않은 이벤트였습니다. 다만 그 때 추가로 만들고 ..