kth990303의 코딩 블로그

정말 기가막히도록 대단한 문제라 생각된다. 문제는 아래와 같다. https://www.acmicpc.net/problem/14574 14574번: 헤븐스 키친 남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 www.acmicpc.net 대충 생각나는 건 수학, 그래프 알고리즘이 생각나지 않는가? 좀 더 생각해보면 MST와 dfs로 연결지을 수 있다. 의식의 흐름 및 해설 이긴 사람은 천국으로 떠나고, 진 사람이 경기를 계속해서 이어갈 수 있는 특이한 룰이다. 즉, 사람 수가 N명일 때, 경기는 N-1번 진행된다. 시청률의 합이 최대가 되도록 해야 하며..

예전에 AC받았다가, 데이터가 추가되면서 WA로 바뀐 문제를 오늘 한번 다시 도전해봤다. https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 난이도가 상당함에도, Solve수가 상당히 많은 문제. kks227님의 블로그에서 SCC 예제문제이기도 하고, 애초에 scc + topology 연습문제로 좋은 문제이기 때문에 많이 풀린 것이 아닐까 예상된다. 오랜만에 scc를 풀어본 것이라 간단하게 해설을 써보겠다. 의식의 흐름 및 해설 단방..

요즘 웹개발 공부를 하느라 백준을 많이 풀지 못해서 풀어본 문제. https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 생긴게 트리dp, DFS처럼 생겨서 해결해보려 한 문제이다. 의식의 흐름 및 해설 사실 맨 처음에 생각난 것은 '인접행렬과 그래프' 이다. 즉, 아래 문제가 먼저 떠오른 것이다. https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,0..

UCPC 2021 본선 D번 문제이다. 본선은 정말 괴수들만 진출하는 곳이 맞긴 한가보다. UCPC 본선 중에서 가장 쉬운 문제들 중 하나라고 한다. https://www.acmicpc.net/problem/22876 22876번: 츠바메가에시 "츠바메가에시"(つばめがえし)는 일본의 검사 "사사키 코지로"가 날아가는 제비를 베었다고 전해지는 검 초식의 이름이다. 기록상으로는 세 번 연속 칼질을 했다고 전해지나, 실제로 기술을 재 www.acmicpc.net 처음에 이 문제에서 tree 배열의 범위를 잘못 생각하여 계속 맞왜틀을 하였다... 의식의 흐름 및 해설 / 테스트케이스 첨부 처음에는 단순히 매 순간의 최댓값 3번을 구하면 된다고 생각하여 세그먼트트리를 이용하여 구현하였다. 주의할 점은 좌표의 범위..

KOI 2014 초등부, 중등부, 고등부 모든 부문에 출제된 문제이다. 초등부 입장에선 꽤나 어려웠을 것 같은 문제. https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 의식의 흐름 및 해설 시계, 반시계의 표현으로 헷갈리게 표현했지만, 결국은 a->b의 방향으로, a>b일 경우 a->(b+N)의 방향으로 간다는 점만 생각하면 된다. 우리를 자주 괴롭히는 원형(circular) 문제이다. 원형으로 문제가 ..

문제 https://www.acmicpc.net/problem/12019 12019번: 동아리방 청소! 첫째 줄에는 N일 까지의 각 사람들이 느낀 불쾌함의 총합의 최솟값을 출력하고 두 번째 줄에는 그 때 청소한 날짜를 오름차순으로 출력한다. 정답이 여러 가지인 경우에는 사전 순으로 앞서는 www.acmicpc.net 알고리즘이 뭔지 파악하기 쉽게 생겨서 무난할 줄 알았는데, 청소한 날짜를 출력하는 부분에서 조금 애를 먹었던 문제. 오늘은 이 문제를 포스팅하려 한다. 의식의 흐름 및 해설 N, M이 굉장히 작다. 시간초과 걱정은 뒤로 미뤄두어도 괜찮을 듯하다. 우선 청소를 언제 할지에 따라 답이 굉장히 다양해지므로 브루트포스 알고리즘이나 DP를 생각할 수 있겠다. 이런 형태의 DP문제를 많이 풀어와서 그런..

문제 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 의식의 흐름 및 해설 처음 볼 때 생각난 것은 당연히 세그먼트트리이다. 세그먼트트리의 정석이라 불릴만한 문제이기 때문이다. 물론 세그먼트트리에 익숙하지 않다면 그리디나 누적합을 떠올릴 수도 있겠지만, 이 문제는 inversing counting 알고리즘과 워낙 유사하여 세그먼트트리를 떠올릴 수밖에 없는 문제이다. 그런데 생각했던 것보다는 조금 더 난이도가 있었다. 바로 '이 값들은 각 ..

문제는 아래와 같다. https://www.acmicpc.net/problem/21923 21923번: 곡예 비행 동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 www.acmicpc.net 그림만 보고 1초 정도 투포인터가 생각난 문제. 재밌어 보이는 문제였는데, 생각보다 삽질을 좀 했다. 간단하게 해설 및 주의포인트들을 살펴보도록 하겠다. 의식의 흐름 및 해설 이 문제같은 경우는 상향으로 비행할 때와 하향으로 비행할 때, dp 점화식이 달라지기 때문에 dp 함수를 2개로 나누는 것이 훨씬 편하다. 처음에는 한꺼번에 처리하려 했으나, if문 남발이 너무 심해져서 따로..

UCPC 2021 예선에 나온 문제이다. 본 대회 당시, 다익스트라+dp로 뇌절쳤던 문제여서 다시 풀어보았다. https://www.acmicpc.net/problem/22358 22358번: 스키장 첫 번째 줄에 다섯 개의 정수 $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$) 가 주어진다. 이후 $M$ 개의 줄에 각 코스의 정보가 세 개의 정수 $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i www.acmicpc.net AC받은 풀이를 먼저 살펴보고, 다익스트라가 안되는 이유를 포스팅하겠다. AC 풀이 N이 최대 10만이지만, 리프트 횟수가 최대 10이다. 또한, l..

문제 https://www.acmicpc.net/problem/15897 15897번: 잘못 구현한 에라토스테네스의 체 성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너 www.acmicpc.net 꽤 어렵게 다가온 수학문제이다. N이 1e9이므로 O(N)은 시간초과가 발생한다. 어떻게 해결해야 할까? Harmonic Lemma (조화수열의 성질) 예시로 N=6인 경우를 들어보자. j의 값은 i의 값이 더해지므로, i의 값이 횟수에 영향을 준다. 맨 처음에 j는 디폴트값으로 1이므로, 1+(N-1)/i의 값이 횟수가 됨을 확인할 수 있다. 그러나, 아직까지는 아래 O(N) ..