본문 바로가기

분류 전체보기

BOJ)1202 보석 도둑 문제: icpc.me/1202 가장 가격이 많이 나가는 보석을 최대한 많이 담아야 원하는 답을 구할 수 있는건 그리디하게 알 수 있다. 그렇기 때문에 우리는 가장 가격이 많이 나가는 보석을 먼저 보며 lower_bound를 이용하여 현재 그 보석을 담을 수 있는 가방이 있느지 확인해주면 된다. 1234567891011121314151617181920212223242526272829303132#include #include #include #include using namespace std;int n, k, x, y;long long r;int main() { scanf("%d%d", &n, &k); priority_queue pq; for (int i = 0; i 더보기
BOJ)14499 주사위 굴리기 문제: icpc.me/14499 문제에서 주어진 조건에 맞게 주사위를 시뮬레이션해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include #include using namespace std;int n, m, x, y, k, a[21][21], dice[6], q;bool chk(int cx, int cy) { return 0 더보기
BOJ)2213 트리의 독립집합 문제: icpc.me/2213 트리에서 각 정점에 대한 가중치가 주어지고 정점들의 가중치를 최대로 가지는 최대독립집합 set을 구하는 문제이다. 트리에서의 최대 독립집합을 구하는 문제이기 때문에 사이클이 존재하지 않으므로 다이나믹 프로그래밍으로 해결할 수 있다. dp[pos][state]로 pos번째 정점에 대한 선택여부를 state로 강제한다면 점화식을 쉽게 세워줄 수 있다. 해당 정점을 선택할 경우 해당 정점에 대한 가중치를 얻고 자식들은 state를 선택안함으로 강제된다. 해당 정점을 선택하지 않을 경우 자식들의 state 결과는 선택하거나 선택안하는 경우 중 최댓값을 가지게 된다. 두 케이스에 따라 점화식을 다르게 세워준 후 다이나믹 프로그래밍을 이용하여 답을 구해준 뒤 역추적을 해주면 된다. 1.. 더보기
BOJ)3770 대한민국 문제:icpc.me/3770 동해안과 서해안을 잇는 고속도로의 셋이 주어질 때 교차점의 수를 구하는 문제이다. 모든 고속도로를 받아서 동해안의 순서로 오름차순 정렬을 해준 뒤 동해안의 순서로 보면서 현재 보고 있는 고속도로보다 전에 봤던 고속도로 중 현재 고속도로보다 서해안이 큰 고속도로들의 수를 구해주면 된다. 이를 효과적으로 계산하기 위하여 세그먼트 트리를 사용해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include using namespace std;int t, n, m, k, x, y, seg[10000];long long r;int update(in.. 더보기
BOJ)6091 핑크 플로이드 문제: icpc.me/6091 플로이드 워셜로 구해진 최단거리의 셋이 주어질 때 원래의 트리에 연결 된 간선만 출력하는 문제이다. 우리는 주어진 최단거리의 셋중에서 가장 작은 간선부터 그리디하게 선택할 수 있다. 근데 이 때 선택하면 안되는 간선을 트리의 성질을 이용하여 알 수 있다. 트리에서 a에서 b로 가는 경로는 유일해야 하므로 내가 현재 보고 있는 간선에 연결 된 양쪽 두 정점이 이미 하나의 컴포넌트를 이루고 있다면 그 간선은 사용하면 안된다. 따라서 우리는 가장 작은 간선부터 연결해 주되 disjoint-set을 이용하여 두 컴포넌트를 연결시켜주어 해당 간선이 컴포넌트를 이루는지 여부를 판단한다. 1234567891011121314151617181920212223242526272829303132.. 더보기
BOJ)1826 연료 채우기 문제:icpc.me/1826 1km를 가는데 1L의 연료가 필요하고 현재 가진 연료량과 목적지까지의 거리 그리고 각 주유소의 정보가 주어질 때 충전횟수를 최소화하여 목적지에 도착하는 충전횟수를 출력하는 문제이다. 우선 주유소의 정보를 받아 거리를 기준으로 sort한 뒤 내가 현재 갈 수 있는 거리보다 가까운 거리에 있는 모든 주유소의 정보를 받아와 채울 수 있는 연료량을 heap에 저장한다. 이후 그리디하게 갈 수 있는 주유소중 가장 큰 연료량을 가지는 주유소를 선택해나가면 문제를 해결 할 수 있다. 123456789101112131415161718192021222324252627#include #include #include using namespace std;priority_queue pq;int n.. 더보기
BOJ)2056 작업 문제: icpc.me/2056 a번 작업을 실행할 때 선행되야 되는 작업 b의 셋이 주어질 때 모든 작업을 완료하는데 걸리는 시간을 출력하는 문제이다. 문제에서 선행관계는 항상 번호가 증가하는 순서로 이루어진다고 하였으므로 사이클이 존재하지 않는 DAG임을 알 수 있다. 따라서 우리는 위상정렬을 해준 뒤 위상정렬의 순서대로 일을 처리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include using namespace std;int n, in[10002], c[10002], x, y, r;vector vt;int main() { scanf("%d", &n); vt.re.. 더보기
BOJ)7579 앱 문제: icpc.me/7579 최소한의 비용을 사용하여 m만큼의 메모리를 얻을 때 비용을 출력하는 문제이다. dp[pos][cost]= pos번째 앱까지 cost만큼의 비용을 사용해 얻을 수 있는 메모리의 최댓값으로 정의 한 뒤 파라메트릭 서치를 이용하여 cost값을 조정해주면 된다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std;int n, cost, m[101], c[101], dp[101][10001];int func(int pos, int cos) { if (pos = 0) ret = max(ret, func(pos - 1, cos - c[pos]) + m.. 더보기
BOJ)2157 여행 문제: icpc.me/2157 번호가 증가하는 순서대로만 여행을 할 때 1번 도시에서 N번 도시까지 항공편을 K번 이하로만 이용하여 갈 때 얻을 수 있는 기내식 점수의 최댓값을 구하는 문제다. dp[pos][val]= pos번 나라까지 여행하고 항공편을 val번 이용했을 때 얻을 수 있는 최대 기내식 점수 로 정의 한 뒤 문제를 해결하면 된다. 소스코드는 탑 다운 방식으로 구현하여 테이블의 정의가 반대다. 123456789101112131415161718192021222324252627#include #include #include #define INF 987654321using namespace std;int a[301][301], n, m, k, dp[301][301], x, y, z;int func.. 더보기
BOJ)2618 경찰차 문제:icpc.me/2618 경찰차 두대가 사건을 순서대로 처리할 때 가장 적은 거리를 이동하도록 사건을 배치하는 경우와 거리를 출력하는 문제이다. dp[x][y] = 경찰차 1이 x번째 사건을 경찰차 2가 y번째 사건을 마지막으로 처리하였을 때 이동한 거리의 합의 최솟값으로 정의한 뒤 문제를 해결해주면 된다. 점화식은 dp[x][y] = min(dp[prev][y]+ dist(prev,x) , dp[x][prev] + dist(prev,y))이다. 소스에서는 바텀업 방식으로 구현하여 테이블의 정의가 약간 바뀌었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#in.. 더보기

티스토리툴바