BOJ 20192 : 순서 섞기 20192번: 순서 섞기 정수가 저장된 크기 N인 배열 A가 있을 때, ‘순서 섞기’ 연산은 아래와 같이 정의된다. 크기가 N인 배열 B를 이용하여, 배열 A의 좌측 끝 또는 우측 끝에 있는 값 중 하나를 차례로 꺼내어 배열 B www.acmicpc.net 관찰이 조금 까다로운 문제이다. 먼저 문제를 관찰하면 수열을 증감 상태로 나타내면 전환되는 점이 있는데, 이를 순서를 바꿀때 전환되는 점이 한번 섞을때 최대 그 반만큼 감소한다는 거다. 그래서 전환점을 O(N)에 찾으면 된다. 바꾼 횟수는 log2(전환점)으로 계산하면 된다. 코드 djayy035/dj035_PS 코드저장소. Contribute to djayy035/dj035_PS development by creati..

www.acmicpc.net/problem/15976 15976번: XCorr $ 1 \le N, M \le 3,000, 1 \le n \le 3,000, -3,000 \le a \le b \le 3,000$ 이다. www.acmicpc.net 처음에는 어려웠는데, 생각해보니 진짜 쉬운 문제였다. 그냥 x_i를 기준으로 해서 범위 안의 y_i를 모두 더한다. 이는 Prefix-Sum을 활용하고, a_i값에 알맞게 범위를 찾아주는 것은 이분 탐색을 활용하거나 표준 라이브러리를 이용한 lower_bound, upper_bound를 이용한다. #include #define MEM 300005 #define sanic ios_base::sync_with_stdio(0) using namespace std; ty..

https://www.acmicpc.net/problem/17623 17623번: 괄호 6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 W에 대하여 정수의 ‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해 www.acmicpc.net 이 문제는 재귀적인 느낌(?)이 있기에 DP로 해결 가능하다. dp[i] = "N=i일때 dmap(X)의 최솟값" 이때 우리는 두 가지 경우를 생각할 수 있다. 첫번째 경우 : 이전 문자열에서 괄호를 감싸는 경우 i가 2,3,5의 배수일 때 처리해주면 된다. 두번째 경우 : 이전 문자열에 갖다 붙일 경우 min(dp[i]+dp[n-i]) & (1