본문 바로가기

분류 전체보기

BOJ)4948 베르트랑 공준 문제: icpc.me/4948 n~2n 사이의 소수의 개수를 출력하면 되는 문제이다. 에라토스테네스의 체로 소수들을 구해 준 뒤 파셜섬의 차를 구해주면 된다. 12345678910111213141516171819202122232425#include #include using namespace std;bool p[270000];int s[270000];int n;int main() { p[0] = p[1] = true; for (int i = 2; i 더보기
BOJ)12842 튀김 소보루 문제: icpc.me/12842 m명의 사람이 튀김 소보루를 먹는 시간이 주어졌을 때 n번째 튀김 소보루를 누가 먹었는지 출력하는 문제이다. n과 m이 10만이고 개인이 소보루를 먹는 시간 t가 최대 1000이여서 시뮬레이션을 돌려도 시간내에 AC 받을 수 있었다. 123456789101112131415161718192021222324#include #include #include using namespace std;int n, s, m, x, r, t;int a[100010];int main() { scanf("%d%d%d", &n, &s, &m); for (int i = 1; i 더보기
BOJ)13505 두수 XOR 문제: icpc.me/13505 N개의 수 중에서 두 수를 정해 XOR한 값이 가장 크게 하는 문제이다. 두수가 XOR을 하여 가장 큰 수가 되려면 서로 다른 비트가 가장 많아야 할 것이다. 트라이를 이용하여 모든 수를 비트 순서대로 저장 한 후 이후 모든 수에 대해서 자기와 다른 비트를 따라가도록 하면 된다. 이때 가장 큰 수가 되야 하므로 비트는 높은 자리 수 부터 검사한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #incl.. 더보기
BOJ)12843 복수전공 문제: icpc.me/12843 n개의 강의가 주어질 때 서로 다른 학부의 강의면서 강의의 내용이 겹치는 강의는 두 강의중 하나만 수강할 때 최대로 수강할 강의 수를 구하는 문제이다. 내용이 겹치는 두 강의를 서로 연결해준다면 c학부와 s학부로 이루어진 이분 그래프가 나타나게 된다. 이때 이분 그래프에서 최대로 매칭되는 만큼 수업을 더 안들으면 되기 때문에 이분 매칭을 구해준 후 N에서 빼주면 답이 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include using namespace std;int n, m, x, y;char .. 더보기
BOJ)12841 정보대 등산 문제: icpc.me/12841 왼쪽 1번 지점에서 오른쪽 n번 지점까지 가는 최단 거리를 구하는데 이 때 횡단보도는 한번 밖에 못 건넌다는 전제가 있다. N개의 횡단보도를 건너는 케이스를 전부 확인을 해줘야 하는데 N이 10만이나 되기 때문에 모든 케이스를 직접 더해줄 경우 TLE를 받을 수 있다. 하지만 Partial sum을 이용한다면 왼쪽 오른쪽길의 횡단보도 기준으로 위 아래는 쉽게 구할 수 있다. 주의 할 점은 10만개의 횡단보도에 거리가 10만 까지 들어올 수 있으므로 long long을 사용해줘야 한다. 12345678910111213141516171819202122232425262728293031#include #include #define INF 999999999987654321using.. 더보기
BOJ)1865 웜홀 문제: icpc.me/1865 방향 그래프에서 시간이 거꾸로 간다는 개념이 나온다면 우선 벨만-포드를 생각해 볼 수 있다. 이때 주의 할 점은 도로는 방향이 없으므로 양 방향에 연결을 해줘야 한다. 문제에서 질문은 출발을 하였을 때 보다 시간이 되돌아 가 있는 경우가 있는지 확인하는 것인데 이것은 벨만-포드에서 음수 사이클 존재 여부를 확인하는 것과 동치다. 따라서 벨만-포드를 구현 한 뒤 음수 사이클 존재 여부에 따라 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #define INF 987654321using namespace std;in.. 더보기
BOJ)11999 Milk Pails 문제: icpc.me/11999 X,Y,M이 주어졌을 때 X와 Y를 이용하여 M을 넘치지 않도록 최대한 얼마나 채울 수 있는지 구하는 문제이다. X,Y,M이 전부 1000이하이기 때문에 이터레이터를 1000번씩 돌려주면 되는 쉬운 문제다.O(N^2) 1234567891011121314151617#include #include using namespace std;int x, y, m, r;int main() { freopen("input.txt", "r", stdin); scanf("%d%d%d", &x, &y, &m); for (int i = 0; i 더보기
BOJ)10775 공항 문제: icpc.me/10775 비행기가 도착하는 순서대로 게이트에 도킹을 하는데 한 게이트에는 오직 한대의 비행기만 도킹이 가능하다 이때 각각의 비행기는 1~g번째 게이트중 하나에 도킹할 수 있다는 정보가 들어올 때 최대로 도킹할 수 있는 비행기의 수를 출력하면 된다. g번째 게이트부터 도킹을 하는게 이득인 것임은 자명하므로 disjoint-set을 이용하여 g게이트에 도킹이 될 경우 다시 g게이트를 확인 할 때 g-1게이트를 확인 하도록 parent를 설정해주면 된다. 만약 find 호출에서 0을 호출하게 된다면 1~g번째 게이트는 모두 사용중인것이니 더 이상 도킹이 불가능 하므로 현재까지 도킹 된 횟수를 출력해 주면 된다. 12345678910111213141516171819202122#includ.. 더보기
BOJ)12845 모두의 마블 문제: icpc.me/12845 인접한 두 카드를 합쳐서 하나로 만들어 점수를 얻는데 이때 카드의 레벨이 합쳐지는 두 카드 중 높은 카드에 의해서 결정이 될 때 획득 할 수 있는 최대 골드를 출력하는 문제이다. 문제를 읽고 파일 합치기나 행렬 곱셈 순서과 유사한 문제로 판단하여 두문제를 푸는데 사용했던 dp기법을 사용하였으나 TLE를 받게 되었다.... 123456789101112131415161718192021222324252627282930313233#include #include #include #define INF 987654321using namespace std;int n;int arr[1010];int dp[1010][1010];int ax[1010][1010];int func(int lo,.. 더보기
BOJ)12846 무서운 아르바이트 문제: icpc.me/12846 알바를 한 기간동안 임금이 가장 적은날을 기준으로 급여를 받을 때 최대 이익을 출력하는 문제이다. 유명한 문제인 히스토그램에서 가장 큰 직사각형과 같은 문제로 해석해도 된다. 세그먼트 트리를 이용하여 최솟값의 위치를 저장한 후 가장 작은 위치를 기준으로 왼쪽 오른쪽을 보며 답을 비교해 나간다. 히스토그램에서 가장 큰 직사각형 문제는 스택으로도 풀 수 있으니 이곳을 참고하도록 하자 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include typedef long long ll;using namespac.. 더보기