본문 바로가기

분류 전체보기

BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다 문제: icpc.me/13016 오랜만에 문제 포스팅을 한다. 문제를 요약하면 한 정점 v에서 다른 정점으로의 최단거리를 dist[i] (i: 1~n) 이라고 했을 때, dist[i]의 최댓값을 모든 정점 v에 대해 구하는 문제이다. 물론 한 정점에서 dist[i]의 최댓값을 구하는건 dfs를 수행하여 쉽게 해결할 수 있지만 모든 정점에 대해 구하게 될 경우 정점의 개수가 5만이므로 시간초과를 보게 될 것이다. 하지만 조금 생각해보면 한 정점에서의 부터 다른 정점으로 부터의 최단 거리 중 최댓값은 트리의 지름의 양 끝 단말 노드 중 하나로의 거리라는 것을 알 수 있다.(만약 트리 지름의 단말 노드가 아닌 다른 리프로 부터의 거리가 최댓값이라면, 트리의 지름보다 긴 거리가 생긴다는 뜻이므로 모순이된다.) .. 더보기
SCPC 2018 이벤트 당첨! 살면서 이런 이벤트와는 인연이 없다고 생각했는데 어제 갑자기 문자가 왔다. 커피 당첨됬다고 ㅋㅋㅋ 올해 SCPC는 본선에 나갈 수 없겠지만(7월 입사 ㅠㅠ... 게다가 일본 여행 날짜와 2차 예선 날짜가 겹친다 ...) 커피라도 받게되서 기분이 좋다 더보기
BOJ)15673 헤븐스 키친2 문제 :http://icpc.me/15673 n개의 수열이 주어질 때, 연속 된 두 구간을 선정을 한다. 두 구간을 a,b라하면 구간 a의 합과 구간 b의 합의 곱의 최댓값을 구하는 문제이다. 생각해보면 구간 a의 합과 구간 b의 합의 최솟값들을 곱하는 경우와, 구간 a의 합과 구간 b의 합의 최댓값들을 곱하는 경우가 답의 후보가 됨을 알 수 있다. 구간 a가 i~j 구간 b가 k~l 이라고 해보자. k를 고정시킨 뒤 생각해보면 구간 k~l의 합은 psum[l]-psum[k-1]이므로, k보다 크거나 같은 범위의 psum의 최댓값과 최솟값을 가지고 있으면, 구간 b의 최댓값과 최솟값을 구할 수 있다. 그럼 i~j 구간의 최댓값과 최솟값은 어떻게 처리할 수 있을까? 구간 i~j의 합은 psum[j]-psu.. 더보기
BOJ)1856 단어 게임 문제: icpc.me/1856 w개의 문자열이 주어진다.길이 l의 문자열을 앞서 주어진 w개의 문자열로만 표현하고 싶을 때 지워야하는 문자의 최소 개수를 출력하는 문제이다.dp[x]=길의 l의 문자열을 길이 x까지 봤을 때 지워야하는 최소 문자의 수로 정의한 뒤 점화식을 세우면dp[x]를 채우기 위해선 w개의 각각의 문자열에 대해서 저 문자를 남기기 위하여 지워야할 개수를 구해주면 l*l*w의 시간복잡도로 디피 테이블을 채울 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include #include using namespace std;int w,l,dp[333];st.. 더보기
BOJ)2171 직사각형의 개수 문제: icpc.me/21712차원 평면위에 5000개 이하의 점이 있을 때 점들로 만들 수 있는 모든 직사각형의 수를 세는 문제이다,n제한이 5000에 2초이므로 n^2logn 솔루션으로 풀 수 있을 것이라고 생각하였다.n*n으로 모든 두 점에 대하여 직사각형의 대각선에 놓이는 경우를 생각하면, 나머지 대각선에 포함되는 두 점은 set을 이용해 존재여부를 log시간에 찾을 수 있다.123456789101112131415161718192021222324252627#include #include #include #include using namespace std;int n,res;set st;vector vt;int main(){ scanf("%d",&n); for(int i=0;i 더보기
BOJ)14943 벼룩 시장 문제: icpc.me/14943벼룩을 사려는 사람과 팔려는 사람이 있을 때 벼룩 거래에 발생하는 비용의 최솟값을 출력하는 문제이다.문제를 잘 읽어보면 사려는 양과 팔려는 양은 같고, 거래에 발생하는 비용이 거래하는 두 사람의 거리에 비례한다.우선 사려는 양과 팔려는 양이 같다는 점을 이용해, 항상 거래가 완전하게 이루어진다는 점을 생각해보면, 그냥 최대한 가깝게 거래를 매칭 시켜주는 그리디한 방법이 답이 된다는 걸 알 수 있다.문제는 n이 10만으로 조금 크기 때문에 매칭을 일일이 직접 해줄 수는 없고, 투 포인터를 이용하여 처리해주면 깔끔하게 구현 가능하다.1234567891011121314151617181920212223242526272829303132333435363738#include #inclu.. 더보기
BOJ)14950 정복자 문제:icpc.me/14950모든 도시를 점거하는데 필요한 최소 비용을 출력하는 문제이다.단 도시를 점거 해 나갈 때 마다 일정 비용이 추가 되었는 데 이것에 포커스를 맞추면 문제가 어려워 질 수 있다.조금 생각을 해보면 결국 모든 도시를 점거해야하기 때문에 MST를 만들어주면 비용을 커버할 수 있는 걸 알 수 있다.이미 MST를 구상하였다면 이에 이용 된 간선은 n-1개로 고정일 것이고, 이는 모든 도시를 점거하는데 필요한 간선의 최소 개수이기도 하기 때문에(1~n-1 까지의 합) x t가 증가하는 비용으로 고정된다.123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using nam.. 더보기
BOJ)15271 친구 팰린드롬2 문제: icpc.me/15271남자와 여자에 대한 이분 그래프가 형성되므로 이분 매칭으로 최대로 세울 수 있는 친구 수를 구해줄 수 있다.1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include using namespace std;int n, m, visited[222], b[222];vector vt;int dfs(int here) { if (visited[here])return false; visited[here] = true; for (auto next : vt[here]) { if (!b[next] || dfs(b[next])) { b[next] = .. 더보기
BOJ)15270 친구 팰린드롬 문제: icpc.me/15270 명시 된 N의 범위가 작으므로 상태DP를 이용하여 해결할 수 있다.dp[state][pos] = state(이미 친구가 된 사람들의 상태를 표현)이고 pos번째 까지 친구 관계를 봤을 때 춤을 추는 인원의 최댓값12345678910111213141516171819202122232425262728#include #include #include using namespace std;int dp[1 더보기
BOJ)14939 불 끄기 문제: icpc.me/14939 언제 봤는지는 기억이 잘 안 나지만 언젠가 한번 봤었던 은근히 well-known 문제이다.첫 줄에 전구를 어떤 방식으로 뒤집는 걸 결정을 했다고 가정하면 그 아래 줄은 바로 위의 전구가 켜져 있는지 여부에 따라서 뒤집기 결정을 그리디하게 할 수 있다.따라서 첫 줄을 뒤집는 모든 경우 (2^10)에 대하여 정해준 뒤, 그리디하게 뒤집어주어 최적의 답을 구하는 것이다. 비슷한 시기에 나온 홍익대학교 경시대회의 전구 끄기 문제도 한번 풀어보면 좋을 것 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #incl.. 더보기