[백준 20193] 화려한 직사각형

이런 류의 문제는 처음 접근 해본다. 되게 오랫동안 고민했으며, 이런 유형의 문제에 되게 약하다는 것을 알게 되었다. 1. 아이디어 얼추 생각나는 풀이는 어떤 \(x\)좌표 \(2\)개를 잡아 그 사이의 간격을 \(dx\)라고 하고, 그 사이의 각 점, 어떤 \(y\)에 대해서 \([y-dx, y]\)이 구간안에 다른 모든 색깔이 포함되는 \(y\)가 존재하는 지 판별하면 어떨까 생각했다. 하지만 어떤 \(x\)좌표를 \(2\)개를 잡는 다는 것은 \(O(N^2)\)개의 구간이 나오기 때문에 이분탐색 아이디어를 적용시켜야된다. 어떤 \(x\)구간을 \([x-R, x]\)라고 두고, \(R\)에 대해 이분탐색을 하고, \(f(R)\) 어떤 \(R\)이하의 화려한 직사각형이 존재하는 가로 변형시켜 이분탐색을..

→2021.11.29

[백준 20192] 순서섞기

https://www.acmicpc.net/problem/20192 완전히 관찰 문제이다. 관찰을 해야되는 요소가 그렇게 많지는 않지만, 생각보다 발상이 어려운 문제, 하지만 발상이 떠오른다면 풀이는 되게 간단하다. 1. 풀이 우리가 할 수 있는 행동은 앞에서 빼거나, 뒤에서 빼거나 둘중 하나를 할 수 있다. 이 행동을 통해서 배열을 최소한의 행동으로 단조 증가형태로 만들려면 배열의 값들을 어떤 규칙으로 관리를 해야된다는 사실을 알 수 있다. 기본적으로 우리는 \(2\)번째 예제를 보고 하나의 관찰을 할 수 있다. 배열이 ↗ ↘ (↗ : 증가하는 형태, ↘ : 감소하는 형태) 이런 형태면 \(1\)번만에 정렬이 가능하다는 점을 관찰할 수 있다. 직접해보면 알 수 있다. 그러면 ↗ ↘ = ↗, ↘↗ = ↘..

→2021.11.29

[백준 19943] 조명등

https://www.acmicpc.net/problem/19943 예선 당일 이 문제를 보고 기하 문제인가? 라고 생각했었다. 왜냐하면 정올에서 생각보다 킬러문제로 기하 부분을 많이내기 때문이다. 하지만 시간도 부족했고, 이런 문제 유형은 어떻게 사고해야되는 지 난감해서 \(2\)솔로 끝냈다. 이 문제를 너무 궁금해서 예선 끝나고 여러 커뮤니티에서 찾아보았다. ConvexHull Trick으로 푸는 것이 정해였다. 약간이나마 dp로도 풀 수 있지 않을까 생각해보았지만 포기하였다. 하지만 너무 이 문제를 풀고 싶어서 ConvexHull Trick도 공부하고 열심히 사고했다. 풀이 1. 조명등 설치 후보 찾기 첫번째로 문제에서 제시하는 조명등을 비추는 비용에 대해서 먼저 구해보자. 위와 같이 조명등을 비추..

→2021.11.29

[백준 18913] Graph Coloring

Constructive 1. 풀이 문제를 간단하게 설명해보자면 간선에 \(14\)가지 색들을 배분할 건데, 이때 \(i->j\;j->k\)색깔이 모두 같은 경우가 없게 배분해주어야 한다. 먼저 한가지 관찰할 수 있는 점이 어떤 정점에서 나가는 간선들이 사용한 색깔 집합을 S라고 하자. 그러면 자연스럽게 이 정점에 들어오는 간선들의 색깔의 집합은 \(C−S\) 일것이다. (\(C\)는 \(14\)가지 색깔의 집합) 다음으로 관찰할 수 있는 것은 어떤 두 정점 \(U,\;V\)가 연결되어 있을 때 색깔이 배분이 안되는 상황을 생각해보자, 각 정점에서 나가는 간선들이 사용한 색깔들의 집합을 \(S_U,S_V\)라고 하고, \(C−S_U\;∩\;S_V\;=\;∅\)인 경우는 안된다.식을 정리하면 \(S_U\;⊆..

→2021.11.29

[백준 19941] 햄버거 분배

https://www.acmicpc.net/problem/19941 생각보다 쉬운 문제였다. 예선때도 시간내에 무난하게 풀었고, 여러 방향으로 사고를 해봐야 된다는 사실을 많이 느꼈다. 이 문제의 경우 부분 문제를 받을 수 있는 풀이와 만점을 받을 수 있는 풀이가 있다. 둘다 모두 작성하도록 하겠다. 1. 40점 풀이 먼저 제가 이 문제를 보고 최대값을 구하는 문제인 것을 보고 dp를 사용하겠구나라고 추측했다. 점화식을 세우는 것은 나쁘지 않았다. $$ solve(i,j) = 현재 i번째 위치이고, 마지막으로 먹은 햄버거가 j번째 일때$$ $$ solve(i, j) = \begin{cases} solve(i+1,j), \mbox{if(arr[i] == H)} \\ max_{max(j,i-k) \le w ..

→2021.11.29

[백준 19939] 박 터뜨리기

https://www.acmicpc.net/problem/19939 Constructive한 문제였다. 하지만 그리 어려운 문제는 아니였다. 1. 풀이 기본적으로 \(1\;2\;3\;4\;...\) 이런 식으로 분배하는 것이 최선이다. 그렇기 때문에 \(n\)이 \(k(k-1)/2\)개 보다 작다면 \(-1\)이다. 만약 \(1\;2\;3\;4\;...\) 이런식으로 분배했다고 치자. 그러면 \(n\)이 \(0\)일 때에는 답은 \(k - 1\)이다. 하지만 \(n\)이 남았다면? 제일 큰 \(4\;3\;2\;1\;...\) 이런 내림차순으로 \(1\)개씩 더해주는 것이다. 그리고 첫번째 원소와 마지막 원소의 차가 곧 답이다. 이 방식이 왜 시간안에 돌아가냐면 \(k = 1000\)일 때 필요한 공의 개..

→2021.11.29