본문 바로가기

알고리즘 관련/BOJ

BOJ)5480 전함 문제: icpc.me/5480 각 레이저가 파괴하는 전함의 무게의 최댓값을 출력하는 문제이다. 우리는 우선 쿼리를 전부 받아 오프라인으로 문제를 풀어볼거다. 일단 x좌표와 y좌표가 10억까지들어올수 있기 때문에 전함과 레이저의 x,y좌표를 모두 받아 각각 좌표압축 해준다. 이후 우리는 x와 y에 대한 세그먼트트리를 각각 생성하여 세그먼트 트리에 레이저의 인덱스의 최솟값을 저장할 것이다. 수직인 레이저는 x세그먼트 트리에 수평인 레이저는 y세그먼트 트리에 레이저의 인덱스를 해당 좌표에 최솟값 업데이트 시켜주면 된다. 이후 전함마다 각각 x,y세그트리에서 최솟값인 인덱스를 받는다 가장 작은 인덱스가 의미하는건 결국 그 전함을 파괴하는 레이저라고 보면 된다. 해당 레이저에 전함의 무게를 최댓값으로 업데이트 시.. 더보기
BOJ)10167 금광 문제: icpc.me/10167 직사각형 모양의 영역으로 금광을 개발 할 때 얻을 수 있는 최대 이익을 구하는 문제이다. 문제를 푸는데 상당히 고생했는데 KOI 2014 중등부 문제인걸 보고 어이가없어서 웃음만 나왔다... 일단 N이 3000이므로 N^2혹은 N^2logN 알고리즘을 사용해야 하는데 처음 생각한것은 x축기준으로 스위핑 하여 y축을 세그먼트 트리 구간합에 업데이트 시키는 작업을 순서대로 하는데이 때 이 작업은 전단계의 점들을 반드시 포함하게 되므로 모든점에 대해서 이 작업을 반복하는 것이다. 이 때 처음에는 최대 구간합을 구하기 위해서 이미 업데이트 된 모든 점이랑 비교하여 구간합의 최댓값을 구했는데 이렇게 할 경우 한점에서 업데이트한 후 구간합의 최댓값을 구하는데 O(NlogN) 여기에 .. 더보기
BOJ)9184 신나는 함수 실행 문제: icpc.me/9184 문제에서 점화식 기저 까지 다 정해주는 진정한 꿀문제가 아닐까 싶다. 당연하게도 그냥 함수를 매번 계산한다면 시간초과가 난다. 하지만 우리는 점화식과 기저를 알고 있으니 이걸 이용해 다이나믹 프로그래밍을 이용하여 계산할때마다 결과를 배열에 저장해주면 된다. 문제에서 하라는대로 하면 쉽게 풀 수 있는 문제이다. 1234567891011121314151617181920212223242526#include #include #include using namespace std;int dp[21][21][21];int a, b, c;int func(int x, int y, int z) { if (x 20) return func(20, 20, 20); int &ret = dp[x][y].. 더보기
BOJ)1049 기타줄 문제: 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.. 더보기
BOJ)2022 사다리 문제: icpc.me/2022 극혐스러운 수학문제이다. 사실 그렇게 어려운 수식은 아니고 직선의 방정식 두개를 구하여 두 교점의 y좌표인 c를 알고 있으니 이때 구해야하는 밑면 m을 이분 탐색을 통하여 찾아 나가는 문제이다. 밑면m이 클수록 c는 낮아지므로 함수로 구한 값이 c보다 크다면 lo를 mid로 c보다 작다면 hi를 mid로 잡아주면 된다. 사실 이터레이터를 얼마나 돌려야되는지 감이 안와서 제출하면서 조절했는데 너무 많이 돌리면 TLE를 보게되고 너무 적게 돌리면 오차때문에 WA를 보게된다. 123456789101112131415161718192021222324252627#include #include using namespace std;double x, y, c, lo, hi;double fx.. 더보기
BOJ)2252 줄 세우기 문제: icpc.me/2252 N명이 학생이 주어지고 두 학생의 키를 비교한 M개의 정보가 주어질 때 줄을 세운 결과를 출력하는 문제이다. 우리는 두 학생의 우선관계를 방향 그래프를 이용하여 설정해준 뒤 topology를 구해주면 된다. 즉 DFS를 돌리면서 먼저 끝나는 순서대로 스택에 저장해준 뒤 하나씩 뽑으면서 출력해주면 답을 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include #define MAX_N 32000using namespace std;vector vt;stack st;int n, m, x, y, visited[MAX_N + 1];void dfs(int .. 더보기
BOJ)1561 놀이 공원 문제:icpc.me/1561 M개의 놀이기구를 순서대로 타는데 각각의 놀이기구의 운행시간이 주어질 때 마지막 아이는 몇번째 놀이기구를 타게되는지 출력하는 문제이다. 우리는 파라메트릭 서치를 이용하여 N명의 인원이 놀이기구를 탑승하는데 걸리는 시간 T를 구할 수 있다. T를 구했다면 T-1초동안 놀이기구를 탄 아이 수를 쉽게 구할 수 있고 이를 K라 했을 때 우리는 O(M)만큼 탐색하여 앞으로 O(N-K)번째로 타게 될 놀이기구의 번호를 구하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include using namespace std;typedef long long ll;ll n, m,.. 더보기
BOJ)1666 최대 증가 직사각형 집합 문제: icpc.me/1666 여러 직사각형이 주어졌을 때 이중 몇개의 직사각형을 골라서 집합을 만들것이다. 이때 집합의 조건은 집합의 임의의 두 원소를 선택했을 때 두 직사각형중 한 직사각형이 다른 한 직사각형보다 오른쪽 위에 있어야한다는 조건이다. 우선 각 원소를 왼쪽 아래 점의 x좌표 기준으로 스위핑하여 문제를 푸려고한다. 우리는 각 원소를 비교해나가며 쿼리를 처리하며 세그먼트 트리에 업데이트 할 것인데 이 때 비교는 왼쪽 아래 점과 하며 업데이트는 오른쪽 윗 점을 할것이다. x좌표 기준으로 정렬을 했기 때문에 우리는 세그먼트 트리에 y좌표의 위치에 업데이트 할 것이다. 이때 좌표압축을 사용해 노드를 줄인다. 하지만 우리는 비교는 왼쪽 아래 점 기준으로 하며 정렬도 왼쪽 아래 점 기준으로 하지만 업.. 더보기
BOJ)3392 화성 지도 문제: icpc.me/3392 지도가 주어졌을 때 전체 지도의 면적을 출력하는 문제이다. X,Y좌표가 최대 3만까지 들어오기 때문에 O(X*Y)완전 탐색으로 문제를 해결하기에는 무리가 있다. 우리는 지도의 세로축들을 쿼리로 관리하여 x좌표 ,y좌표1, y좌표2 그리고 끝나는 변인지 시작하는 변인지 변수로 관리를 해준다. 이제 쿼리들을 X좌표 기준으로 정렬을 해보자. 쿼리를 순서대로 볼건데 시작하는 변인 쿼리는 y1~y2구간을 1씩 증가시켜줄것이고 끝나는 변인 쿼리는 y1~y2구간을 1씩 감소시켜 줄것이다. 쿼리를 세그먼트 트리에 업데이트 해주기 전에 우리는 가장 최근에 처리한 쿼리의 x좌표와 현재 처리중인 x좌표의 차이를 dx라고 할때 현재 확인중인 x좌표까지의 면적을 dx*(업데이트 된 y좌표의 개수).. 더보기
BOJ)2336 굉장한 학생 문제:icpc.me/2336 N명이 학생이 세번의 시험을 치뤘을 때 A라는 학생이 B라는 학생보다 세번의 시험의 성적이 모두 좋다면 A가 B보다 '대단하다'고 한다. 어떤 학생 C가 자신보다 대단한 학생이 없을 경우 C는 '굉장하다'라고 한다. N명의 학생의 3번의 시험에서의 등수가 주어졌을 때 굉장한 학생의 수를 구하는 문제이다. 굉장한 학생을 다시 정의하자면 자기보다 세번의 시험을 전부 다 잘본 학생이 한명도 없는 경우이다. 우리는 굉장한 학생을 구하기 위해 첫번째 시험의 등수 기준으로 정렬을 할 것이다. 그리고 첫번째 시험을 잘 본 순서대로 쿼리를 처리할 것이다. 이러면 먼저 나온 학생이 적어도 그 뒤에 나온 학생들보다 1번째 시험을 잘봤다는 것은 자명한 사실이니 뒤에 나오는 학생들의 2,3번째 시.. 더보기

티스토리툴바