문제 분석 -- 선을 여러 번 긋되 중복된 것은 한 번만 세는 문제이다. 이 경우 선을 정렬하여 계산해야 하는데, 어떤 기준으로 정렬을 수행해야 하는가? 끝나는 시간 기준(WA) 시작 시간 기준(AC) 바로 말하자면 시작 시간 기준이다. 끝나는 시간을 기준으로 오름차순 정렬할 경우 다음 선이 이전 선보다 전에 시작해서 나중에 끝날 경우 전에 시작한 부분을 고려하지 못해 WA를 받게 된다. 시작시간을 기준으로 할 경우 다음 선의 시작이 이전 선의 끝보다 먼저인지 나중인지만 고려하고, 매 선의 끝을 저장하면 해결 가능하다. 아이디어만 생각하면 코딩은 어렵지 않다. 사실상 아이디어가 난이도를 골드5까지 올려놓은듯 하다.

최소 신장 트리의 복수 -- 최소 신장 트리는 그래프의 모든 vertices를 연결했을 때 edge 가중치의 합이 최소가 되도록 하는 것을 말한다. 그런데 이 문제는 분명 N개의 행성을 N-1개의 터널로 잇는다는 점에서 최소 신장 트리는 맞는데 뭔가 이상하다. 모든 행성끼리 연결되어있는 구조이다. 심지어 행성의 개수는 최대 10만개이다. 벌써 머리가 지끈거린다... 크루스칼? 프림? -- 내가 예전에 푼 문제는 전부 크루스칼을 사용하였다. 이유는 단지 크루스칼로 푸는게 더 쉬워서기도 했고, 둘 다 상관없었다. 일단 이번 문제에서 노드는 다른 노드와 전부 연결, 즉 fully-connected graph이기 때문에 간선 개수 E는 V(V-1)/2개이다. O(ElogE)인 크루스칼보다는 O(ElogV)인 프림을 쓰는 것이 조금 더 효율적이다. 그러나 log 안에 있기 때문에 2배 차이가 난다는 점에서 드라마틱한 시간 감소 효과를 보기는 어렵다. 피보나치 힙을 쓰면 O(E+log

서론 전에도 선분 교차 문제를 풀었던 기억이 있는데, 그때는 두 선분의 각 끝점의 위치만 주어지고 교차 여부를 0 또는 1로 출력하는 것이 다였다. 그러나 이번에는 다량의 선분을 뭉탱이로 입력받고, 교차된 선분들끼리 그룹핑하는 작업까지 추가되었다. 딱봐도 Union-Find를 사용하면 되는 직관적인 문제이기에 이 부분에서는 문제가 없었는데, 선분 교차 판정 방법을 살짝 까먹어서 다시 복습 겸 찾아보았다. CCW 알고리즘 먼저 선분 교차 판정은 CCW(반시계방향) 알고리즘을 사용하는 것이 정석 풀이이다. 예전에 이 방법을 몰라서 선분끼리 기울기 구하고 난리치다 나누기 연산때문에 애먹은 기억이 난다. 아무튼 그렇게 하면 조건 분기가 매우 많아지고 오류도 생기므로 기왕이면 CCW를 사용하는 것이 낫다. CCW란 한 벡터와 한 점이 주어졌을 때, 해당 점이 벡터의 시계방향에 위치해있는지, 반시계방향인지, 벡터 선상에 위치해있는지 판별하는 알고리즘이다. 벡터

문제 분석 -- 백트래킹 문제, 노가다 문제이다. 대각선 방향으로 이동하므로 x+y, x-y로 묶어서 계산한다. 그런데 그냥 백트래킹으로 접근하면 TLE가 발생한다. TLE 회피 아이디어 -- 비숍은 체스판에서 같은 색상으로밖에 이동할 수 없다는 점을 이용하여, 2개의 문제로 나누어 답을 구한 뒤 둘을 합치면 원래 문제에 대한 답을 구할 수 있다. 이 경우 TLE는 아니지만, pypy3으로 10s가 넘는(AC라고는 나오지만) 시간이 걸린다. 문제 채점 priority가 낮아서 그런가보다. 반면 꽤 빠른 시간으로 푸는 풀이가 존재하는데, 이는 더 분석해봐야 겠다. 문제 -- https://www.acmicpc.net/problem/1799

초벌 실행 안해봐도 TLE일 것 같은 감이 딱 온다... 심지어 티어도 골드1이라서 이렇게 쉽게 풀릴 리 만무함. 정석 풀이 아무리 시도해도 안풀려서 태그를 참고했다. 분할정복을 이용한 거듭제곱이라니... 팩토리얼 구할 때 푸는 방식을 사용해야 하나보다. 그렇다면 곱할 때마다 가짓수가 업데이트되는 인접 행렬을 만들어야 된다. 특정 row에서 출발, column에 도착하는 길이 있을 때 1로 두고 없으면 0으로 두면, 다음과 같은 2차원 인접 행렬이 생성된다. 이제 행렬에 특성에 의해 O(logN) 시간복잡도를 가지는 거듭제곱을 사용하여 풀 수 있다. 행렬을 곱한 횟수만큼 이동한 가짓수가 업데이트된다. 시작점은 0번째 index이므로 시작 행렬은 전부 0에 0 부분만 1로 두면 된다. 이는 각 노드에 대해 정해진 횟수만큼 모든 특정 출발지와 도착지에 대해 이동 가능한 가짓수를 파악하는 방식으로 적합한 풀이방식이다. 인접 행렬을 이렇게

쉬운 계단 수 -- 먼저 모든 가짓수를 세는 방법은 다음과 같다. 각 숫자의 가짓수를 파악하면서 진행해본다. 초기는 0 제외 모두 1, 0은 0이다.이다. 0123456789 0111111111 다음으로 넘어가면 0123456789 1122222221 그 다음은 0123456789 1334444432 최종 출력을 구하기 위해서는 각 가짓수 아래의 수를 모두 더하면 된다. 쉬운 계단 수 문제의 해답이다. 계단 수 -- 근데 이번 문제는 0~9까지의 모든 수가 등장하는 계단 수의 개수를 구해야 한다. 따라서, 해당 계단 수가 어떤 숫자들을 포함하고 있는지도 구분을 해야 한다. 0~9까지의 숫자를 모두 고려할 경우 1024가지의 경우가 나오는데, 비트마스킹 기법을 활용하여 공간을 절약하면 TLE나 MLE 없이 AC받을 수 있다. 즉 쉬운 계단수 문제에서 차원을 한 단계 확장하고, 비트마스킹을 사용하여