$1*n$크기의 체스판이 있다.($n$은 짝수) 체스판은 검흰검흰검흰...순서로 색칠되어있다. 정확히 $n / 2$개의 돌이 체스판위에 놓여져있다. 이 돌들을 움직여서 모두 같은 색깔위에 놓이게 하고싶다. 모두 검정색위에 놓이든 흰색위에 놓이든 상관없다. 이때 돌들이 움직이는 거리의 합의 최소값을 구하는 문제다.
모두 검정칸에 놓는 경우와 흰색칸에 놓는 경우 두 경우를 모두 해보아야한다. 검정칸이든 흰색칸이든 첫 번째 색깔칸에는 가장 왼쪽에 있는 돌이 가야 최소다. 두 번째 색깔칸에는 가장 왼쪽에서 두 번째 있는 돌이 가야 최소다.
난 엄청 복잡하게 풀었는데 풀이보니 엄청 간단하게 풀었다.
두 번 틀렸는데 첫 번째는 조금 복잡하게 푸는 바람에 초기에 들어온 돌들은 다른 배열에 다시 저장해 놓아야 했는데(돌릴 때 저장된 돌들의 위치가 바꾸기 때문에 검정칸, 흰칸 2번 돌려야되서 저장해놓아야한다.) 저장한다고 생각해놓고 바쁜마음에 그냥 제출해버렸다. 두 번째는 예제가 정렬되서 들어오길래 정렬되서 입력되는가 싶었는데 아니였다.. sort해주고 바로 AC받았다.
한 번 켜지면 꺼지지 않는 전구들이 $m$개 있다. 그리고 $n$개의 버튼들이 있는데 각 버튼들은 0개 혹은 여러개의 전구를 켤 수 있다. $n$개의 버튼을 모두 누르면 모든 전구들이 켜지는 것이 보장된다. 이때, 필요없는 하나의 버튼들 안 누르고 싶다. 즉, $n - 1$개의 버튼만 눌러서 모든 전구들을 켤 수 있으면 YES를, 안 되면 NO를 출력하는 문제다.
들어온 크기 $m$인 $n$줄의 배열의 합을 저장해보자. 모든 전구가 켜지는게 보장되어 있으므로 배열의 합의 각 원소값은 1이상임이 보장되어 있고, 배열의 값이 2 이상인 녀석은 켜져 있음에도 불구하고 다시 스위치가 눌러져 켜지게 되는 전구다. 2번 이상 켜지는 전구를 구했고, 2번 이상 켜지는 전구만 켜는 스위치가 1개라도 있으면 YES고 없으면 NO다.
총 $m = n * k$개의 나무판자가 있다. 이 나무판자들로 총 $n$개의 나무통을 만드려 한다. 각 나무통은 $k$개의 나무판자로 만들 수 있다. 나무통의 부피는 나무통을 이루는 나무판자들 중 가장 작은 녀석의 크기다. 이렇게 나무통을 모두 만들 때, 아무 두 나무통의 부피의 차가 $l$보다 작거나 같아야한다. 이 조건들을 만족시키며 나무통을 모두 $n$개 만들고 난 뒤 나무통의 부피의 합의 최대값을 구하는 문제다.
아무 두 나무통의 부피차가 $l$보다 작거나 같아야하므로 $v_{가장큰}(v_b) - v_{가장작은}(v_s) <= l$이여야한다. 나무통의 부피는 가장 작은 나무판자의 크기이므로 모든 나무통 중 가장 부피가 작은 나무통의 부피는 가장 작은 나무판자의 크기다. 가장 작은 나무통의 부피를 알았으므로 $v_b <= v_s + l$ 로 $v_b$의 범위를 알 수 있다.
