돌이 코딩하는 방

문제 링크 : www.acmicpc.net/problem/19935 문제 소개 k 판의 게임을 진행한다. 각각의 게임은 m개의 숫자카드중 일부가 있는 n개의 카드 세트에서 1개씩을 뽑는다. 주최측이 원하는대로 수를 선정하고, 그 수와 뽑은 n개의 수의 차이의 절댓값 만큼 점수를 얻는다. 이때 주최측은 얻는 점수가 최소화 되도록 수를 선정한다. 이때 k 판을 진행하면서 얻는 점수가 최대가 되도록 각 판에서 뽑을 숫자카드를 설정하고, 이때 얻을 점수를 구하여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 이 문제를 시작한 이유. 1분 보고 나서 DP 느낌이 확 왔다. 뭔가 난이도의 대부분은 관찰이고, 구현은 그렇게 어렵지 않을 것 같다는 생각이 크..

문제 링크 : www.acmicpc.net/problem/19934 문제 소개 인접행렬이 주어진다. 이때 모든 값은 3이하이다. 이때 주어진 인접행렬을 만족하는 트리가 있는지 판단하고, 있다면 그 트리를 보여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 경로의 가짓수로 가능한 것은 0,1,2,3 인데, 각각의 경우에 대해서 두 노드가 어떤 식으로 배치 되어 있을지에 대해서 생각을 해보았다. 0가지일때: 둘은 같은 컴포넌트에 존재하지 않는다. 또한 0 이 아닌 두 노드는 항상 같은 컴포넌트에 존재해야 한다. 따라서 우리는 경우의 수가 0이 아닌 모든 쌍에 대해서 union &find 를 이용하여 같은 컴포넌트로 묶을 수 있다. 이때 같은 컴포넌..