column이 $n$인 맵에서 테트리스를 한다. 테트리스의 블럭은 항상 $1 * 1$짜리가 들어온다. 블럭이 떨어지는 column이 전부 주어지면 총 지워지는 줄 수를 출력하는 문제다.
풀이는 생략.
문제제목을 안 보고 문제부터 읽었는데 문제이해가 너무 어려웠다. 테트리스의 규칙자체를 전부 설명하다보니 이해가 잘 안 됬는데 문제 풀고나니 문제제목이 보여서 실소가 났다.
강의를 듣는데 총 $n$분 듣는다. 매 $i_{th}$분 마다 $a_i$개의 공식을 교수님이 설명해준다. 강의중간에 졸게 되는 경우가 있는데, $t_i$가 1이면 $i_{th}$분에 깨어있는 것이고, 0이면 $i_{th}$분에 졸고 있는 것이며 공식을 듣지 못한다. 강의 중간에 딱 한 번 $k$분동안 안 조는 방법이 있다. 이때 들을 수 있는 공식의 개수의 최대값을 구하는 문제다.
부분합으로 O($n$)에 풀 수 있다. 부분합을 사용할 때에는 배열의 index를 1부터 시작하는게 훨씬 간단해지므로 그렇게 설명하겠다. sum1[i]를 [1, i]까지의 $a_i$의 합이라 정의하고 sum2[i]를 [1, i]까지의 $t_i$가 1일 때 $a_i$의 합 으로 정의하자. 그럼 $i_{th}$분에 안 조는 방법을 써서 $k$분 동안 깨어있게 될 경우 총 공식 수는 $(sum1[i + k - 1] - sum1[i - 1]) + sum2[i - 1] + (sum2[n] - sum2[i + k - 1])$이다. i를 1부터 $n$까지 돌려주면 된다.
startIndex를 1로 잡는 것이 조금 어색해서 문제 난이도에 비해 오래걸렸다.
체스판을 떨어뜨려서 정확히 4조각이 났다. 게다가 몇몇 칸의 색깔도 다른 색깔로 바뀌어버렸다. 다시 4조각을 조립하여 완전한 체스판으로 만들려고 한다. 완전한 체스판을 만들기 위해 바꿔야하는 체스판의 칸의 개수의 최소값을 구하는 문제다. 체스판을 회전하거나 뒤집어서는 안 된다.
일단, 완전한 체스판의 경우는 2가지다. 검정색으로 시작하거나 흰색으로 시작하거나. $n$이 홀 수임이 문제에서 보장되어 있으므로, 완전한 체스판이 검정색으로 시작하면 두 개의 조각은 검정으로 시작, 나머지 두 조각은 흰색으로 시작할것이며, 흰색으로 시작하는 경우도 마찮가지다.
각 체스판조각이 흰색으로 시작할 경우와 검정색으로 시작할 경우 2개 경우의 칸 색깔 변경횟수를 저장해놓은 뒤 4개중 2개를 골라 흰색으로, 나머지를 검정색으로 골라주면 된다. $4C2 = 6$으로 6경우 모두 해주거나 완전탐색으로 때려줘도 된다.
$n$개의 점이 주어진다. 직선 2개를 그어 점들을 모두 두 직선 중 한 개 이상의 직선위에 올릴 수 있는지 판단하는 문제다. 두 직선은 동일한 직선이어도 된다.
일단, 아이디어는 한 점을 잡고, 그 점을 기준으로 다른 점들과 기울기를 측정한 후, 같은 기울기 상에 있는 점이 가장 많은 녀석에게 선을 1개 긋는다. 그 다음 남은 점들을 보는데 남은 점 들이 모두 일직선상에 있으면 2개의 선으로 모두 커버가 되는 것이므로 YES이며, 남은 점들 중 하나라도 직선상에 못 올라오면 2개의 선으로 커버가 안 되므로 NO다.
문제는 이렇게 풀 경우 처음 직선을 그으려고 기준으로 잡는 점의 위치가 중요해진다. 첫 번째 예제의 경우를 막 회전시켜보면 오름차순으로 정렬시켜 왼쪽 아래에서 시작하는 경우에 예외가 생김을 알 수 있다. 따라서 왼쪽아래, 오른쪽아래, 왼쪽위, 오른쪽위 4번 모두 체크해보고 1번이라도 되면 YES를, 모두 안 되면 NO를 출력하면 된다.
조금 야매로 푼 감이 있는데 어쨋든 맞았으니 장땡이지. 아이디어는 문제 보자마자 생각했는데 3번이나 틀렸다. 한 번은 런타임에러 뜨는 바람에(MAX_N을 10만이 아니고 1만으로 해버렸다.) 한 번 틀리고, 한 번은 위에서 언급한 예외를 생각하긴 했는데 그런 tc를 못 만들어서 그냥 돌려봤는데 틀렸다. 마지막 한 번은 예제에서 주어진 tc로 예외 찾아서 바로 적용해보고, 가끔 abs가 이상한 짓을 하는 경우가 발생해서 abs를 모두 max(x, -x)로 바꾸어 주었는데 딱 하나를 max(x, -x)로 해야할걸 max(x, -y)로 해버리는 바람에 틀렸다. 런타임에러랑 오타만 처음부터 잡았으면 1번틀리고 맞출 수 있었는데 아숩다.
드라마의 시즌별로 에피소드 개수가 주어진다. 검색시스템의 문제로 $x$시즌의 $y$에피소드를 검색하면 $y$시즌의 $x$도 뜨는 오류가 발생한다. 이런 오류의 개수를 세는 문제다.
$i$시즌의 에피소드가 $a_i$개 있다면, $[i + 1, a_i]$범위에서 $i$보다 큰 에피소드를 갖고 있는 시즌과 헷갈리게 되므로 이 때 오류가 발생한다. 매번 $[i + 1, a_i]$범위에서 $i$보다 큰 값을 가진 원소의 개수를 세는 쿼리가 $n$번 들어오게 되므로 세그먼트트리를 생각해 볼 수 있다. 다만, 일반적인 세그먼트트리로는 불가능하며 mergesortedTree나 persistentTree로 처리해줄 수 있다. mergesortedTree는 세그먼트처럼 각 범위를 node로 갖고 있는데, 배열의 각 범위의 대표값이 아닌 배열의 각 범위를 정렬한 vector를 node로 갖고 있다. 두 작은 범위가 정렬되어있으면 두 범위를 합쳐 다시 정렬된 배열을 만드는 함수는 c++에서 merge함수로 구현되어 있고, 이 작업이 mergesort와 똑같은 작업이므로 mergesortedTree이다. 이렇게 각 범위를 모두 정렬해놓은 값을 갖고 있으면 $[i + 1, a_i]$범위에서 $i$보다 큰 값을 찾는 query는 lower_bound로 빠르게 처리가능하다.
persistentTree는 세그먼트트리를 $n$개 만들 때 $n^2$이 되는 공간복잡도를 O($nlogn$)으로 줄여주는 tree라고 알고 있다. 아직 공부한 적이 없으므로 persistentTree는 생략.
풀이를 보니 fenwikTree로 때리는 것 같길래 semgentTree로 풀려고 머리를 굴려봤는데 무슨 수를 써도 방도가 안 나와서 그냥 mergesortedTree로 처리했다. 이전에 구현해봤을 뿐만 아니라 update과정이 없으므로 segmentTree보다 구현이 간단한 편이다. 문제 자체는 처음 mergesortedTree와 persistentTree를 들어본 BOJ - K번째 숫자보다 쉬운것 같다.
