뉴비의 PS 낙서장

https://www.acmicpc.net/problem/17958 17958번: Cycle String? In the first example, substrings of the restored string are: “abbab”, “bbabc”, “babcb”, “abcbc”, “bcbcc”, “cbccb”, “bccba”, “ccbab”, “cbabb”, “babba”. Note that the first example does not contain repetitions, however www.acmicpc.net 일단 \(NO\)가 되는 조건을 알아보자. 1. 등장하는 문자가 1개인 경우 ex)\(aa...a\) 2. 등장하는 문자가 2개고, 한 문자가 \(2N-2\)개 이상인 경우 ex) \(aa..

https://www.acmicpc.net/problem/4011 4011번: 기름 파기 첫 번째 줄에는 세 개의 정수 M, N, K가 주어지는데, M과 N은 각각 직사각형 격자의 행과 열 개수이고 K는 한 사업자가 입찰에 응할 수 있는 정사각형 구역 한 변의 크기이다. 다음 M개의 줄에는 각 www.acmicpc.net 구역을 최대 3개만 팔 수 있기 때문에 여러가지 경우를 구상해 볼 수 있다. 총 6가지 경우가 있다. 왼쪽 위에서 부터 시작하는 DP, 오른쪽 위에서 부터 시작하는 DP, 왼쪽 아래에서 부터 시작하는 DP, 오른쪽 아래에서 부터 시작하는 DP테이블을 만든다. DP테이블의 정의는 \(dp[i][j]\) : 시작점부터 \((i,j\))까지 의 영역에서 기름을 파낼 한 구간을 구할 때 최대 ..

https://www.acmicpc.net/problem/1665 1665번: 화물열차 첫째 줄에는 화물 열차 A에 연속적으로 컨테이너가 놓여 있는 구간의 개수 N이 주어진다. 이어 N줄에는 Xi와 Yi (Xi ≤ Yi)가 공백을 사이에 두고 주어지는데 이는 화물 열차 A의 Xi칸부터 Yi칸까지 컨 www.acmicpc.net 이렇게 총 5개의 상황이 벌어질 수 있고, 두 시작점이 만나는 시점부터 컨테이너가 만나는 칸 수가 늘어나다가, A의 시작이 B의 끝을 만나거나, A의 끝이 B의 시작을 만나는 경우가 생기면 칸 수가 유지되다가 하락한다. 그러다 두 끝점이 만나는 시점부터는 컨테이너가 만나는 칸 수가 0이 유지된다. 이 기울기 함수들을 누적합으로 관리해서 최대로 컨테이너 끼리 만나는 칸 수가 몇인지 ..