분류 전체보기 (231) 썸네일형 리스트형 큰 수 만들기 그냥 그리디로 풀면 되는 문제이다.정렬을 하는데 정렬 기준만 정해주면 되는데, a, b가 있을 때 ab와 ba를 비교하면 된다.처음에는 자릿수로 따지면서 맨앞이 큰 순서대로 하고, 겹치는 경우에 대한 예외 처리를 하려다 보니 너무 복잡해졌는데 생각보다 간단하게 해결할 수 있었다.#include#include#include#includeusing namespace std;int N;string arr[1004];bool compare(string a, string b){ string ab = a+b; string ba = b+a; if(ab>ba) return true; else return false;}int main(){ scanf("%d",&N); for(int i=1.. 숨바꼭질 5 수빈이가 이동한 위치에 동생이 나중에 오게 된다면, -1, +1을 반복하면서 기다릴 수 있는데시간 차이가 짝수여야 가능하다.이 부분만 잘 처리하면 간단한 문제가 된다.visit[i][j]를 i는 시간%2, j는 위치로 해서 체크하면 된다.그렇게 bfs로 visit 배열을 채워나가면 되는 간단한 문제이다.#include#includeusing namespace std;int N,K;queue>pos;int visit[2][500004];int mov(int p,int type){ if(type==0) return p-1; else if(type==1) return p+1; else return p*2;}int bfs(){ pos.push(make_pair(N,0)); visit[.. 고층 빌딩 엄청 간단한 문제인데 생각보다 고민을 많이 했다.dp로 풀어야 된다는 걸 알고 보면 쉬운데 dp[i][j][k]를 빌딩 i개, 왼쪽에서 본 개수가 j, 오른쪽에서 본 개수가 k일 때 가능한 경우의 수로 정의하면 된다.그러면 빌딩이 i-1개였을 때 빌딩 하나를 추가한다는 느낌으로 생각해보면dp[i][j][k]=dp[i-1][j-1][k]+dp[i-1][j][k-1]+dp[i-1][j][k]*(i-2) 이렇게 식을 세울 수 있다.#includelong long div = 1000000007;long long dp[104][104][104];long long build(int n,int l,int r){ if(dp[n][l][r]!=0) return dp[n][l][r]; if(l==0 || r==.. 정점들의 거리 이전에 풀었던 lca 알고리즘을 사용하면 되는 문제이다.https://bluesunset-hack.tistory.com/214 LCA 2제목에서부터 나와있듯 그냥 LCA 알고리즘을 구현하라는 문제이다.정점에서부터 하나씩 부모 노드로 거슬러 올라가게 되면 시간이 너무 많이 걸리기 때문에2의 거듭제곱 단위로 끊어서 거슬러bluesunset-hack.tistory.comlca를 사용해서 공통부모를 찾고, 공통부모까지의 거리의 합을 출력하면 끝이다.#include#includeusing namespace std;int depth[40004];int N,M;struct Data{ int num, dist;}parent[40004][30];vectornodes[40004];int height;void dfs(.. 임계경로 임계경로 알고리즘 문제이다.위상정렬과 역방향 그래프를 이용해야 하는 알고리즘인데 구해야 하는 것이 만나는 시간과 쉬지 않아야 하는 도로의 수이다.우선 만나는 시간부터 구하면, 특정 도시에 도착하는 데 가장 오래 걸리는 시간을 maxtime에 저장한다.그리고 그 도시에서 다른 도시로 넘어갈 때 넘어간 도시의 maxtime을 갱신해주는 방식으로 하면 되는데이때 도시를 순회하는 순서를 위상정렬로 정렬된 결과를 이용하면 된다. 위상정렬에 대해 간단하게 설명하자면, 순서가 정해져 있는 작업을 할 때 순서가 어긋나지 않게 정렬해주는 알고리즘이다.진입차수라는 개념을 사용하는데, 정점으로 들어오는 경로의 수를 degree에 저장해서 진입차수가 0인 정점들을 큐에 넣고정점과 이어진 정점들의 진입차수를 1씩 빼고 다시 진.. 사탕상자 간단한 세그트리 응용 문제이다.세그트리에는 1부터 1000000까지의 맛이 각각 몇개 들어있는지 저장하면 된다.쿼리가 약간 다른데, 순위가 x인 사탕의 맛을 찾으려면 x가 seg[n*2]보다 크면 x에서 seg[n*2]를 빼고 seg[n*2+1]로 이동하면 되고,작으면 seg[n*2]로 이동하면 된다.#includeint N;long long M=1000000;long long seg[4000004];void update(long long n, long long s, long long e, long long ind, long long v){ if(ind어렵지 않으니 update와 find 함수 부분만 보면 바로 이해할 수 있다. 선분 그룹 이 문제는 왜 플레에 있는지 모르겠을 정도로 간단한데, 그냥 선분교차에 대한 처리 방법만 알면 된다.선분이 교차한다는 것은 한 선분을 기준으로, 나머지 선분의 두 점이 각각 다른 방향에 존재하는 것이다.여기서 방향은 전에 풀었던 convex-hull 에서 배웠던 ccw 함수를 쓰면 된다.그런데 방향이 달라도 직선이 아니라 선분이기 때문에 교차하지 않을 수 있다.따라서 한 선분만 기준으로 검사하는 것이 아니라, 각 선분을 기준으로 삼아서 검사를 두번 진행해야 한다.그리고 한가지 경우를 더 처리해야 하는데, 두 선분의 점 4개가 모두 일직선에 있을 경우이다.이 때는 한 선분의 max 꼭짓점이 다른 선분의 min꼭짓점보다 크기만 하면 교차한다. 이렇게 교차 여부 검사 함수만 짜면, 나머지는 그냥 이중for문을.. 전깃줄-2 교차하지 않게 하기 위해서 없애야 하는 전깃줄을 구하는 것은 교차하지 않게 남길 수 있는 전깃줄의 최대 개수를 구하는것과 동일한다. 그리고 이것은 가장 긴 증가하는 부분수열과 같은 문제가 된다.없애야 하는 전깃줄 번호도 구해야 하기 때문에 이전에 풀었던 가장 긴 증가하는 부분수열 문제를 그냥 그대로 이용하면 된다.#include#include#includeusing namespace std;int N;vector>lines;vector lis;vector last;int ind[100004];void solve(){ for(auto i=lines.begin();i=0;i--) { if(ind[i]==ans) { //last.push_back(i); .. 이전 1 2 3 4 5 6 ··· 29 다음
