henry's PS diary

https://www.acmicpc.net/problem/14003 LIS 배열을 구할 때 길이는 구할 수 있지만 실제 LIS의 순서를 보장하지는 않는다. 하지만 마지막 값이 정답의 마지막값임은 보장한다. 이 정보를 p 배열에 따로 담은 후 LIS 배열을 구한 후에 마지막 값의 인덱스를 이용해서 역추적하면 실제 LIS를 구할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include using namespace std;typedef pair pii; int n,a[1000000],p[1000000];vector l; bool..

https://www.acmicpc.net/problem/12015 lower_bound를 이용해서 O(nlogn)만에 LIS를 만들 수 있다. 직접 예제들을 만들어서 동작 과정을 살펴보면 이해가 쉽다. 1234567891011121314151617181920#include #include #include using namespace std; int main(){ int n,m; scanf("%d",&n); vector l; l.push_back(-1); while(n--) { scanf("%d",&m); if(l.back()

https://www.acmicpc.net/problem/5639 preorder의 순서인 root->left->right을 이용해서 재귀적으로 범위를 설정해서 postorder의 순서인 left->right->root로 바꾼다. 123456789101112131415161718192021#include int n,a[10001]; void go(int l,int r){ if(l>r) return; int m=l; while(a[++m]

https://www.acmicpc.net/problem/1174 1038 감소하는 수와 같은 문제이다. 이번에는 비트마스크를 이용해서 모든 경우를 저장해서 답을 찾는다. 123456789101112131415161718192021222324#include #include #include typedef long long ll;using namespace std; int n;vector v; int main(){ for(int i=1;i

https://www.acmicpc.net/problem/1038 d[i][j] = i자리이면서 오른쪽 끝자리가 j인 감소하는 수의 개수 라고 하자. 그러면 d[i][j]는 하나 작은 자리수이면서 끝자리가 j보다 큰 수들에다가 j를 붙이면 된다. 따라서 d[i][j] += d[i-1][k] (j+1

https://www.acmicpc.net/problem/15971 두 로봇의 위치 사이의 거리에서 가장 큰 비용의 간선을 빼주면 된다. 그러면 최소 비용으로 양쪽에서 오다가 서로 만날 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include using namespace std; int n,s,e,u,v,w,c[100001],ans,f;vector a[100001]; void dfs(int now,int cost,int mcost){ c[now]=true; if(f) return; if(now==e) { f=1; ans=cost-mcost; return; } for(auto i..

https://www.acmicpc.net/problem/11723 비트마스크를 이용해서 집합 연산을 하는 문제이다. 예를 들어 1을 원소로 가지고 있다면 10, 2를 가지고 있다면 100, 1~5를 가지고 있다면 111110이다. 시프트 연산자를 이용해서 다양한 연산을 할 수 있다. add: x만큼 왼쪽으로 민 것과 OR 연산을 한다. 원소가 이미 존재하면 그대로 1일 것이고 없다면 1로 바뀌어서 추가된다.remove: x만큼 왼쪽으로 민 것을 반전시켜주고 AND 연산을 한다. 그러면 삭제하고자 하는 위치는 무조건 0이 되고 나머지 부분은 유지된다.check: x만큼 왼쪽으로 민 것과 AND 연산을 해서 그대로 유지되면 x가 있는 것이고 0이 되면 x가 없는 것이다.toggle: x만큼 왼쪽으로 민 것..

https://www.acmicpc.net/problem/2098 d[i][j] = 마지막 방문 도시가 i이면서 방문 상태가 j일 때 최소 비용 방문 상태를 비트마스크를 이용해서 정수 하나로 효율적으로 나타낼 수 있다. 시간 복잡도는 O(N^2*2^N)이다. 123456789101112131415161718192021222324252627282930313233#include #include #include #define INF 987654321using namespace std; int n,w[16][16],d[16][1

https://www.acmicpc.net/problem/1563 d[i][j][k] = i일까지 지각 j번, 최근 연속 결석 k번한 출결정보의 수 123456789101112131415161718192021222324#include #define MOD 1000000 int n,d[1001][2][3],ans; int main(){ d[0][0][0]=1; for(int i=1;i

https://www.acmicpc.net/problem/2224 1234567891011121314151617181920212223242526#include int n,i,j,k,cnt,d[52][52];char a[3000][2];int ctoi(char c) { return c>='A' && c