kth990303의 코딩 블로그

고인물들 사이에선 웰노운이라길래 풀어봤는데, 엄청 어렵진 않지만, 이게 어떻게 웰노운인가... 싶은 문제. 처음 문제를 보면 단순 레이지세그를 돌리면 되는거 아닌가 싶어 쉽게 생각했는데, 그렇지 않다. 문제는 아래와 같다. https://www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net 의식의 흐름 및 해설 처음에는 단순히 update_lazy를 두 개 만들어서 하..

나름 유명한 문제인데, 내가 아직 이걸 안풀었다는 사실을 알고 시도해본 문제. 내가 treeDp에 약해서 그런건진 모르겠는데 생각보다 좀 틀렸다. (2회 WA, 3회째 AC) https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net tree dp 중에선 꽤나 웰노운이라 해서 포스팅해보려 한다. 의식의 흐름 및 해설 트리에서의 노드를 포함하는지의 여부에 따라 최댓값이 달라지는 흔한 treedp 유형이다. 그럼에도 불구하고,..

아이디어는 크게 어렵지 않으나, 시간이 상당히 빡빡한 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/19700 19700번: 수업 키가 188cm, 154cm인 학생들을 한 팀으로, 키가 180cm, 161cm인 학생들을 한 팀으로, 키가 172cm인 학생을 혼자 팀으로 묶으면 총 3개의 팀을 구성할 수 있다. 더 적은 갯수의 팀으로 학생들을 묶을 수 있 www.acmicpc.net 의식의 흐름 및 해설 팀에서 자신보다 키가 큰 학생들이 Ki명 이상이면 수업을 째버리겠다는 굉장히 이상한 수강생들만 존재하는 수업이다. 나중에 사회생활은 어떻게 하려는거지 ㄷㄷ 이는 자신보다 키가 큰 학생이 Ki-1명 이하여야 한다는 소리이며, 키큰 순서대로 등수를 매길 때, Ki ..

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