henry's PS diary

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

https://www.acmicpc.net/problem/6135 1234567891011121314151617#include #include #define INF 987654321using namespace std; int n,m,t,u,v,w,i,j,k,d[301][301]; int main(){ scanf("%d %d %d",&n,&m,&t); for(i=1;i

https://www.acmicpc.net/problem/11562 플로이드를 돌려서 어찌어찌 해야할 것 같다. 약간의 트릭을 주면 된다. u,v,b를 받아서 양방향 간선이면 d[u][v]=d[v][u]=0, 단방향 간선이면 d[u][v]=0,d[v][u]=1로 줘서 양방향 간선으로 만들어 준다. 그리고 플로이드를 돌리면 모든 정점 사이에 대해서 최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 하는지 알 수 있다. 123456789101112131415161718#include #include #define INF 987654321using namespace std; int n,m,u,v,b,k,s,e,i,j,d[300][300]; int main(){ scanf("%d %d",&n,&m); for..