전체 글 썸네일형 리스트형 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.. 더보기 이전 1 ··· 3 4 5 6 7 8 9 ··· 118 다음