https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 재밌는 문제이다. 우리는 느낌상 레이지 세그를 생각할 수 있지만, 더하는 값이 등차수열이기에 어떻게 해야할지 고민해봐야 한다. 이때, 우리는 인접한 두 배열 원소의 차이를 세그트리 원소로 하여 생각해보면, 결국 등차수열로 더하는게 어떤 구간 전체에 1을 더하는 것이랑 동치가 된다. 이때 두 원소의 차이를 저장하는 세그먼트 트리이기 때문에 구간의 마지막 원소를..

https://www.acmicpc.net/problem/1023 1023번: 괄호 문자열 괄호 문자열은 다음과 같이 정의 한다. 빈 문자열은 괄호 문자열이다. S가 괄호 문자열일 때, (S)도 괄호 문자열이다. S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다. 모든 괄호 문자열은 위의 www.acmicpc.net 를 먼저 풀고 오는걸 추천한다. 17428번: K번째 괄호 문자열 첫째 줄에 K번째 괄호 문자열을 출력한다. K번째 괄호 문자열이 없는 경우에는 -1을 출력한다. www.acmicpc.net dp[a][b][c] = 크기 a, b='('갯수 - ')'갯수, b c라고 할때, 만들 수 있는 괄호 ㄴㄴ 문자열의 갯수 b

https://www.acmicpc.net/problem/17428 17428번: K번째 괄호 문자열 첫째 줄에 K번째 괄호 문자열을 출력한다. K번째 괄호 문자열이 없는 경우에는 -1을 출력한다. www.acmicpc.net 걍 dp문제인데 재밌다. dp[i][j] = 길이가 i이고, 완성되지 않은 괄호쌍이 j개일 때 만들 수 있는 괄호쌍 갯수 dp[i][j] = dp[i+1][j+1] ('('를 넣을 때) + dp[i+1][j-1] (')'를 넣을 때) 문자열 구하는건 간단하다. "'('를 넣을 때"와 "')'를 넣을 때"를 분리해서 K번째 문자열을 구해주면 된다. 코드

https://www.acmicpc.net/problem/1187 1187번: 숫자 놀이 2N - 1개(N = 2k, 1 ≤ k ≤ 10)의 정수가 있다. 주어진 수 중 임의로 N개를 뽑았을 때 이 합이 N으로 나누어떨어지도록 하는 N개의 수를 출력하는 것이 문제이다. 답이 여러 개일 경우 아무거나 한 개 www.acmicpc.net 문제가 아주 좋으니 충분히 고민해보고 풀길 바란다. 먼저 이 문제에서 안되는 경우가 있는지 확인해보자. 일단 k=1일때는 비둘기집 원리에 의해 항상 답이 있다는 것을 알 수 있다. 그렇다면 여기서 귀납법을 이용해보자. k = n-1일때 무조건 성립한다고 가정하자. k = n일때, 2^(n+1)-1개의 원소가 있을것이며, 이를 2^(n-1)개의 원소가 들어가 있는 그룹 3개와..

https://www.acmicpc.net/problem/16764 16764번: Cowpatibility Here, cow 4 is not compatible with any of cows 1, 2, or 3, and cows 1 and 3 are also not compatible. www.acmicpc.net 가능한 조합을 모두 맵에 저장해놓고 포함 베제 원리를 이용하면 된다. (가능한 모든 조합 - 1개짜리 + 2개짜리 - 3개짜리 + 4개짜리 - 5개짜리) 자세한건 코드 참고.

https://www.acmicpc.net/problem/6171 Naive한 dp로 먼저 생각해보자. dp[i] = i번째 땅까지 샀을 때의 비용의 최솟값 dp[i] = min(dp[j-1]+max(w[k])*max(h[k])) (0