kth990303의 코딩 블로그

우연의 일치로 두번 연속 Farmer John님을 영접하게 됐다. 개인적으로 Farmer John이 나오는 문제를 좋아하는데, 이유는 걍 재밌어서다. 문제는 아래와 같다. https://www.acmicpc.net/problem/14168 14168번: Cow Checklist Every day, Farmer John walks through his pasture to check on the well-being of each of his cows. On his farm he has two breeds of cows, Holsteins and Guernseys. His H Holsteins are conveniently numbered 1…H, and his G Guernseys are convenient..

나름 유명한 문제인데, 내가 아직 이걸 안풀었다는 사실을 알고 시도해본 문제. 내가 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/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문 남발이 너무 심해져서 따로..

dp문제를 풀다가 어서 아이디어 까먹기 전에 기록해야겠다고 생각해 허겁지겁 포스팅하게 되었습니다. (원래 오늘 안쓰려 했는데 ㅠㅠ) www.acmicpc.net/problem/2229 2229번: 조 짜기 알고스팟 캠프에 N(1≤N≤1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 학 www.acmicpc.net 백준 2229번. 조 짜기 문제입니다. 이 문제는 친구가 추천해준 문제인데, 개인적으로 저한테는 생각보다 얻어갈 점이 많아서 좋았던 문제입니다. 의식의 흐름. 처음엔 문제를 잘못 읽어서 pair로 나이, 점수를 저장시켜야 된다고 생각해 꽤나 어려운 dp라 생각했습니다. 그런데, ..

오늘은 그래프와 dp를 모두 좋아하시는 분이라면 아주 신이 날 문제(...)를 리뷰하게 됐습니다! www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 바로 백준 15681번. 트리와 쿼리 문제입니다~~ ???: 아니, 골드5잖아요? 왜 제목엔 실버 상위권이라 써놨습니까?!? 저는 제목에 solved.ac 티어를 쓰기보다는, 제가 생각하는 이 문제의 난이도를 씁니다. 대체로, solved.ac 티어는 ..