생각날때마다 올리는 블로그

링크http://icpc.me/1185문제1. 모든 마을을 최소 한 번씩은 방문해봐야 한다.2. 반드시 출발한 곳으로 돌아와야 한다.3. 출발점은 "임의로" 설정할 수 있다. 이 때 최소 코스트를 출력하라 풀이핵심은 "다시 돌아와야 한다"라는 것이다.일단, 출발점은 임의로 설정할 수 있고, MST 특성 상 어떤 곳에서 시작해도 상관이 없음을 생각하면그냥 그리디스럽게 방문할 때 가장 작은 코스트가 드는 곳에서 시작하면 된다.예제를 생각해보면, 4번 마을을 방문할 때 코스트가 6으로 제일 적으므로 4번에서 시작하는 것이다.이제 어떻게 방문할지를 생각해봐야 한다. 관찰을 해보면, 다시 자기자신으로 돌아와야 한다는 특징 때문에, 간선을 무조건 "짝수"번 들러야 함을 알 수 있다.MST 특성 상 사이클은 없으므로..

링크http://icpc.me/7453 문제네 개의 배열 A, B, C, D가 주어질 때, A[a]+B[b]+C[c]+D[d]=0이 되는 (a, b, c, d)의 순서쌍의 갯수즉, 걍 아무거나 네 개 뽑아서 더했을 때 0되게 하는 갯수 풀이먼저, $N\leq4000$임을 생각해야한다.이를 왜 생각해야하느냐?만약 완전탐색 기법으로 A, B, C, D 모든 배열 훑으면서 쓰으으윽 하면 $O(N^4)$이된다.$4000=4\times10^3$이고, $4000^4=2^8\times10^{12}$인데 이를 1초내에 돌리는건 그냥 불가능하다...따라서 좀 더 효율적은 방법을 생각해보아야 한다! Key-Idea : Meet in the Middle영어로 까리하게 Meet in the middle인데 한국어로 직역하면 ..

https://www.acmicpc.net/problem/1071문제$N$개의 숫자가 주어진다. 이 때, $A[i]+1\neq A[i+1]$이 되지 않게 숫자의 순서를 바꾸고자 한다.만약 답이 여러개면 사전순으로 제일 빠른 것을 출력하라. 풀이풀이의 시작은 제일 빠른에 있다.제일 빠른 것을 출력할려면 일단 숫자를 최대한 작게 하되 "필요할 때만" 바꿔줘야 한다.예를 들어서 1 3 4 4 이렇게 있으면 굳이 안바꿔도 위 조건을 만족시키기 때문에 상관이 없다는 것이다.하지만 3 4 4 1 이렇게 인풋이 들어오면 1이 제일 앞에 오게 바꿔줘야 한다. 따라서 먼저 들어온 input들을 정렬해서 그 이후 순서를 적절히 바꿔줘야 함을 알 수 있다.이제 정렬되었다고 가정하자. $A_i,\ A_{i+1},\ \cdot..