본문 바로가기

전체 글

BOJ)5012 불만 정렬 문제: icpc.me/5012 iAk를 만족하는 경우의 수를 세는 문제이다. 우리는 j를 기준으로 생각해보자. 현재 j를 보고 있을 때 경우의 수에 해당할 수 있는 경우는 result = SUM [ (j보다 먼저 등장하고 Aj보다 큰 수) x (j보다 나중에 등장하고 Aj보다 작은 수) ] 으로 나타낼 수 있다. 따라서 우리는 쿼리를 다 받은 후 앞에서 부터 보면서 j보다 먼저 등장하면서 Aj보다 큰 수들을 먼저 기록 한 후 다시 한번 뒤에서부터 보면서 j보다 늦게 등장하면서 Aj보다 작은 수들을 기록해준 뒤 곱해주어 더한값을 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #in.. 더보기
BOJ)3002 아날로그 다이얼 문제: icpc.me/3002 N개의 다이얼이 주어졌을 때 구간이 주어지면 구간의 합을 구한뒤 구간의 수를 전부 1씩 증가시켜주는 문제이다. 얼핏보면 구간에 대한 증가연산과 구간합을 출력하면 되니 레이지 프라퍼게이션을 이용한 구간합으로 바로 해결할 수 있을것 같지만 문제는 다이얼이기 때문에 9를 증가시키면 0이 된다는 것이다. 결국 0~8의 숫자는 증가시킬 경우 1씩증가하게 되지만 9는 증가시킬 경우 오히려 -9가 되버린다. 이래서 구간에 대한 합을 한번에 노드에 저장하고 있을 경우 증가연산이 애매해질 우려가 있다. 따라서 우리는 구간마다 노드를 10개씩 만들어 0~9까지의 개수를 저장하여 값을 증가시키는 경우 0~9 ->(0+x)%10~(9+x)%10까지로 쉬프트 시킬것이다. 물론 구간에 대한 증가가 .. 더보기
BOJ)1168 조세퍼스 문제2 문제: icpc.me/1168 N명의 사람이 원을 이루며 앉아있고 M번째 사람을 제거하면서 진행할 때 제거되는 순서에 따른 순열을 출력하는 문제이다. 세그먼트 트리를 이용하여 현재 위치에서 M번째 사람을 찾아내서 풀면 된다. 이때 주의 할 점은 환형이기 때문에 남아있는 사람수를 고려하여 모듈러 연산이 필요하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include using namespace std;int seg[400040];int n, m;vector ans;int update(int pos, int val, int node, .. 더보기

티스토리툴바