Problem Solving/BaekJoon (10) 썸네일형 리스트형 4386 별자리 만들기 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 전형적인 Minimum Spanning Tree 문제이다. 입력으로 별의 x, y 좌표를 받아서 Complete Graph가 되도록 모든 별들 사이의 간선을 만들어준다. 그리고 이제부턴 크루스칼 알고리즘을 적용해서 간선을 정렬해서 최소 비용의 간선부터 루프를 생성하지 않으면 선택하는 식으로 풀면 된다. 간단한 문제였는데, 오랜만에 풀다 보니 사소한 데서 에러가 좀 있었다. 그리고 코드도 좀 더럽게 짠 거 같기도 하고... 꾸준히 풀어야 겠다. C++ 더보기 #in.. 2624 동전 바꿔주기 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 전형적인 DP 문제이다. 이차원 배열 dp를 만들고 dp[i][j]에는 i번째 동전까지 사용했을 때, j원을 만들 수 있는 가능한 경우의 수를 저장하는 방식으로 해결했다. C++ 더보기 #include #include using namespace std; int cnt, k; int main(void) { cin.tie(nullptr); ios_base::sync_with_stdio(false); int t; cin >> t >> k; vecto.. 이전 1 2 다음
