본문 바로가기

분류 전체보기

BOJ)13549 숨바꼭질3 문제:icpc.me/13549 X의 위치에서 1초후에 X+1혹은 X-1로 이동가능하고 순간이동을 할경우 0초후에 2*X위치로 이동가능할 때 K까지 가는 가장 빠른 시간을 출력하는 문제이다. 각 좌표를 정점으로 생각하여 다익스트라를 돌리면 된다. 12345678910111213141516171819202122232425262728#include #include #include #include using namespace std;int dp[250000], n, k;int main() { scanf("%d%d", &n, &k); memset(dp, -1, sizeof(dp)); priority_queue pq; pq.push({ 0, n }); while (pq.size()) { int here = pq.t.. 더보기
BOJ)2910 빈도 정렬 문제: icpc.me/2910 수열이 존재할 때 수열에서 가장 많이 등장하는 빈도로 정렬을 하는 문제이다. 이 때 빈도가 같은 수는 먼저 등장한 순서대로 정렬을 해야한다. 우리는 수가 최대 10억까지 들어올 수 있으므로 빈도를 저장하기 위해 키값에 따른 값을 저장할 수 있는 map 자료 구조를 사용할 수 있다. 두개의 맵을 선언하여 하나는 빈도수를 하나는 들어온 순서를 저장한 뒤 벡터에 빈도수와 키값을 삽입 시켜준 뒤 조건에 맞게 정렬을 해준 뒤 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132#include #include #include #include using namespace std;int n, c, x;map mp;map m;.. 더보기
BOJ)7795 먹을 것인가 먹힐 것인가 문제: icpc.me/7795 A집합과 B집합이 주어졌을 때 A집합의 어떤 수 X가 B집합의 어떤 수 Y보다 큰 경우의 수의 합을 출력하는 문제이다. A집합과 B집합의 크기 N M은 20000까지 들어올 수 있으니 O(N*M)의 방법으로 완전탐색한다면 한번의 테스트 케이스에서도 간당간당한데 여러번의 테스트 케이스를 거친다면 TLE를 보게 될 것이다. 우리는 B집합을 정렬한 후 lower_bound를 이용하여 N개의 쿼리에서 각각 X보다 작은 수 Y의 개수를 구할 수 있다. 시간 복잡도는 O((N+M)logM)이 될 것이다. 12345678910111213141516171819202122232425262728#include #include #include using namespace std;int t, n.. 더보기
BOJ)3758 KCPC 문제: icpc.me/3758 KCPC대회에서 각팀의 스코어가 주어졌을 때 정해진 기준에 따라 순위를 출력하는 문제이다. 제출 횟수나 최종 제출 시간은 쿼리를 받으면서 업데이트 시켜주면 되지만 최종 점수 같은 경우는 제출한 모든 기록중 문제당 최댓값이 업데이트 되므로 배열을 만들어 따로 저장해준 후에 업데이트 시켜준 뒤 조건에 맞게 정렬해주면 쉽게 구할 수 있는 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std;int t, n, k, id, m, a, b, c;int g[101][101];struct student{ .. 더보기
BOJ)8983 사냥꾼 문제: icpc.me/8983 KOI 2013 중,고등부 문제이다. N마리의 동물들의 위치가 좌표로 주어지고 x축위에 M개의 사대가 존재하는데 이때 모든 사대의 사정거리는 공통적으로 L이다. 각 사대에서 동물들과의 거리는 [abs(x(동물)-x(사로))+y(동물)] 로 계산될 때 사냥 가능한 동물의 수를 출력하는 문제이다. N과 M이 최대 10만까지 그리고 사정거리와 좌표는 1~ 1억까지 들어온다. 우리는 모든 사대와 각 동물들을 비교할 경우 O(N*M)의 시간 복잡도로 TLE를 보게 된다는 걸 알고 있다. 따라서 최대 NlogN의 알고리즘이 필요하다. 우리는 우선 동물들을 x좌표 기준으로 정렬 ,그리고 사대도 x좌표 기준으로 정렬을 할 것이다. 그 다음 동물들을 볼건데 어떤 동물 A를 사냥 가능한 사대.. 더보기
BOJ)10277 JuQueen 문제: icpc.me/10277 C개의 코어가 있을 때 쿼리를 받아 3종류의 연산을 처리해주면 되는 문제이다. 단 코어의 하한선은 0이고 상한선은 N으로 입력으로 주어진다. 쿼리는 다음과 같다 change X S 코어X를 S만큼 증가시켜라groupchange A B S 코어 A부터 코어B까지 전부 S만큼 증가시켜라state X 코어X의 값을 출력하라 단, 코어를 증가시키다가 상한이나 하한에 다다를시 증가를 멈춘다. change나 groupchange 같은 경우 증가혹은 감소시킨 계수를 출력해야 하는데 우리는 코어를 증가시키다 상한이나 하한에 도달하는 경우를 판단해야한다. 따라서 우리는 구간에 대한 최댓값 최솟값을 세그먼트 트리로 관리하여 구간을 증가 시킬 시 상한혹은 하한에 도달하는지 여부를 판단하여 상.. 더보기
BOJ)2877 4와 7 문제:icpc.me/2877 4와 7로만 이루어진 수 중에서 K번째로 작은 수를 출력하는 문제이다. 각 숫자가 4와 7로만 이루어졌기 때문에 우리는 N의 자리 수는 2^N개 밖에 존재하지 않는다는걸 알 수 있다. 이를 이용하여 K번째로 작은 수가 L자리수라는 걸 알 수 있다. 이후 L자리에서 V번째로 작은 수는 결국 이진수로 생각하면 비트가 1인 수는 '7' 비트가 0인 수는 '4'가 된다. 따라서 V의 각 비트를 조사하여 답을 출력해주면 된다. 12345678910111213141516171819202122232425#include #include using namespace std;int k, a[31], l;int main() { for (int i = 0; i 더보기
BOJ)2775 부녀회장이 될테야 문제: icpc.me/2775 a층 b호에 사는 주민은 a-1층의 1~b호까지의 주민의 합일때 k층n호에 사는 주민의 수를 출력하는 문제이다. 사실 k와 n의 범위가 매우 작기 때문에 그때 그때 구해줘도 TLE를 받을일은 없을것 같지만 우리는 배운 사람들이니까 다이나믹 프로그래밍을 통하여 쉽게 답을 구 할수 있다. 점화식은 dp[i][j]=dp[i-1][j]+dp[i][j-1] 이다. 12345678910111213141516171819#include #include using namespace std;int dp[15][15], t, k, n;int main() { for (int i = 1; i 더보기
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) 여기에 .. 더보기

티스토리툴바