ACM-ICPC 상 탈 사람

문제: icpc.me/14943벼룩을 사려는 사람과 팔려는 사람이 있을 때 벼룩 거래에 발생하는 비용의 최솟값을 출력하는 문제이다.문제를 잘 읽어보면 사려는 양과 팔려는 양은 같고, 거래에 발생하는 비용이 거래하는 두 사람의 거리에 비례한다.우선 사려는 양과 팔려는 양이 같다는 점을 이용해, 항상 거래가 완전하게 이루어진다는 점을 생각해보면, 그냥 최대한 가깝게 거래를 매칭 시켜주는 그리디한 방법이 답이 된다는 걸 알 수 있다.문제는 n이 10만으로 조금 크기 때문에 매칭을 일일이 직접 해줄 수는 없고, 투 포인터를 이용하여 처리해주면 깔끔하게 구현 가능하다.1234567891011121314151617181920212223242526272829303132333435363738#include #inclu..

문제: icpc.me/14939 언제 봤는지는 기억이 잘 안 나지만 언젠가 한번 봤었던 은근히 well-known 문제이다.첫 줄에 전구를 어떤 방식으로 뒤집는 걸 결정을 했다고 가정하면 그 아래 줄은 바로 위의 전구가 켜져 있는지 여부에 따라서 뒤집기 결정을 그리디하게 할 수 있다.따라서 첫 줄을 뒤집는 모든 경우 (2^10)에 대하여 정해준 뒤, 그리디하게 뒤집어주어 최적의 답을 구하는 것이다. 비슷한 시기에 나온 홍익대학교 경시대회의 전구 끄기 문제도 한번 풀어보면 좋을 것 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #incl..

문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2851 확실한 번역은 모르겠지만 대략적인 설명은 간선이 주어질 때 해당 간선에 연결 된 두정점중 하나는 반드시 소프트웨어가 설치되어야 할 때 최소비용으로 소프트웨어를 설치하는 방법을 출력하는 문제이다. 소프트웨어 설치비용은 i번 정점의 경우 2^i의 비용이 소모된다. 즉 i번 정점에 소프트웨어를 설치하는건 0~i-1번 정점 모두에 소프트웨어를 설치하는것보다 비싸다 그렇기 때문에 최대한 작은 정점에 소프트웨어를 설치해야한다. 이를 위하여 간선에 연결 된 두 정점 중 작은 정점에 설치를 해야함은 자명하다. 그렇다면 이제 문제는 간..

문제: icpc.me/12963 N개의 정점과 M개의 간선으로 이루어진 그래프에서 0번정점에서 N-1번 정점으로 이동 가능한 사람의 최대 수를 구하는 문제이다. 얼핏보면 그냥 0번 정점에서 N-1번 정점으로의 maximum flow를 구하는 문제로 볼 수 있겠지만 한가지 문제가 있다. 간선의 capacity가 너무 커지기 때문에 modulo작업이 필수가 되는데 이와 같은 환경에서 maximum flow를 잘 처리해줄 수가 없기 때문이다. 따라서 우리는 조금 그리디하게 접근을 해야한다. 그래프에서 가장 큰 간선의 가중치는 나머지 모든 간선의 가중치의 합보다 크기 때문에 그 간선으로 이동가능한 경우가 그리디하게 최대가 된다. 그렇기 때문에 그 간선을 연결해보고 0에서 N-1 정점으로 이동가능하면 그 가중치만..

문제:icpc.me/1826 1km를 가는데 1L의 연료가 필요하고 현재 가진 연료량과 목적지까지의 거리 그리고 각 주유소의 정보가 주어질 때 충전횟수를 최소화하여 목적지에 도착하는 충전횟수를 출력하는 문제이다. 우선 주유소의 정보를 받아 거리를 기준으로 sort한 뒤 내가 현재 갈 수 있는 거리보다 가까운 거리에 있는 모든 주유소의 정보를 받아와 채울 수 있는 연료량을 heap에 저장한다. 이후 그리디하게 갈 수 있는 주유소중 가장 큰 연료량을 가지는 주유소를 선택해나가면 문제를 해결 할 수 있다. 123456789101112131415161718192021222324252627#include #include #include using namespace std;priority_queue pq;int n..

문제: icpc.me/1201 N M K 가 주어질 때 1~N까지의 수로 이루어진 수열에서 최대 부분 증가 수열의 길이가 M이고 최대 부분 감소 수열의 길이가 M인 수열을 출력하는 문제이다. 우리는 부분 감소 수열의 개수 K개의 세그먼트를 만들면서 하나의 세그먼트는 전부 증가하는 수로 이루어져 있으며 그 세그먼트의 최대 길이는 M이 되도록 만들어주면 된다. M+K-1

문제: icpc.me/13560 n개의 축구 팀이 존재할 때 각 축구 팀의 승수가 주어진다. 각 축구팀들 끼리는 무조건 한번의 경기가 열리며 승패가 반드시 갈린다고 할 때 주어진 축구팀의 승수의 셋이 valid 한지의 여부를 묻는 문제이다. 우리는 승수를 받은 뒤 sort해준 다음 승수가 적은 팀부터 큰 팀으로 볼 건데 승수가 작은 팀은 승수가 현재 주어진 셋에서 큰팀한테 졌다고 가정하여 팀을 하나씩 삭제하는 방법으로 그리디하게 접근해줄 것이다. 도중에 내가 이긴팀이 남은 팀보다 많거나 내가 이긴팀의 수가 0보다 작은 경우가 생기면 invalid하다고 판단해주면 된다. 1234567891011121314151617181920212223#include #include #define MAX_N 10000us..

문제: icpc.me/1049 N개의 기타 줄을 새로 교체하려고 할때 6개로 사는 묶음 가격과 낱개로 구매하는 가격이 M번 주어진다. 이때 기타 줄을 교체하는데 사용되는 최소비용을 구하는 문제이다. 우리는 당연히 들어오는 M개의 입력중에 최솟값만 처리해주면 된다. 그리고 각 최소 가격에 대해서 6개 묶음의 가격을 A 낱개의 가격을 B라고 할때 A>6*B 라면 무조건 낱개로 구매해주면 되고 아닌경우에는 (N/6)*A+(N%6)*B를 출력해주면 된다. 라고 생각할 수 있겠지만 안타깝게도 6개 미만인 낱개를 살 때 낱개로 1~5개 보다 6개짜리 묶음을 사는게 더 싼 케이스가 들어온다. 따로 예외 처리해주면 된다. 123456789101112131415161718192021#include #include #de..