문제 링크https://www.acmicpc.net/problem/15927 어려워 보였는데 https://blog.naver.com/pasdfq 이 블로그 운영하시는 분이 큰 힌트를 주셔서 쉽게 풀었다.매우 간단한데, 다음의 케이스만 보면 된다. 1) 문자열 전체가 회문이 아니면 답은 문자열의 길이이다.2) 문자열 전체가 회문이다. 2-1) 문자열 전체가 모두 같은 문자일 때 팰린드롬이 아닌 부분 문자열이 존재하지 않으므로 답은 -1이다. 2-2) 위의 상황이 아니라면, 처음 또는 끝의 문자 하나만 제외한 문자열은 팰린드롬이 아니게 된다. 따라서 답은 (원래 문자열의 길이 - 1)이다. 정답 코드 질문 및 피드백 환영합니다.
문제 링크 https://www.acmicpc.net/problem/15926 우선 스택을 이용해 $O(N)$의 시간복잡도로 올바른 괄호문자열의 여는 괄호, 닫는 괄호의 위치를 저장할 수 있다. 문자열 $s$와 배열 $d$에 대해$d[i]$가 1인 경우 $s[i]$가 올바른 괄호문자열에 포함되는 괄호이고, 0인 경우 아니라고 하자.$s[i] = $ '(' 이면 스택에 위치 i를 넣고, $s[j]$에서 $s[i]$와 쌍이 되는 닫는 괄호가 나오면 $s[i]$와 $s[j]$는 올바른 괄호 문자열에 포함되는 괄호이므로 $d[i] = d[j] = 1$이다. 스택으로 올바른 괄호문자열의 위치들을 저장했으니 배열 $d$에서 1이 최대로 연속되는 값이 답이다. 예를 들어, (())()(()의 경우 idx 0 1 2 ..
문제 링크https://www.acmicpc.net/problem/15925 사용 여부가 1이든 0이든 풀이는 같으니 0이라고 가정하고, N크기가 어떻든 풀이는 같으니 N = 5라고 가정하자. N*N 정사각형에서 한 행을 보자. 이런 경우는 전부 0으로 만들 수 있으므로 한행을 전부 0으로 만든다. 이런 경우 행의 차원에서는 1을 0으로 바꿀 방법이 없다.그럼 저 1은 누가 0으로 바꿀 수 있을까? 바로 해당 칸의 열에서 바꿀 수 있다. 마찬가지로 한 열을 봤을 때 이런 경우에 저 1들은 해당 칸의 행에서만 0으로 바꿀 수 있다. 행 차원에서 모든 행을 먼저 탐색하고, 그 후 모든 열을 탐색하면 행의 차원에서만 봤을 때 바꾸지 못했던 1들의 값이 결정될테고, 다시 행을 훑어보면서 한 행을 0으로 바꿀지 ..
문제 링크 https://www.acmicpc.net/problem/15924 구사과씨가 어디서 출발할지 모른다. 따라서 각각의 모든 점에서 X까지 갈 수 있는 경우의 수를 모두 구해서 더해야 한다. 역으로 X에서부터 시작해 뒤쪽에서 앞쪽으로 올 수 있는 경우의 수를 저장하자. $d[i][j] = (i, j)$에서 X까지 갈 수 있는 경로의 수 $p[i][j] = $ 직사각형 지도에서 $(i, j)$의 정보 $\left\{\begin{array}{c}d[i-1][j] = d[i-1][j] + d[i][j],\text{ if }\ i - 1 \geq 0 \text{ and } p[i-1][j] = \text{'S' or 'B'} \\ d[i][j-1] = d[i][j-1] + d[i][j],\text{ i..
문제 링크 https://www.acmicpc.net/problem/15922 문제를 풀기 위해 수직선들을 좌표가 낮은 순으로 정렬하자. 그리고 앞의 수직선부터 탐색한다. 인접한 두 수직선의 관계는 다음과 같다. 빨간 선의 양 끝점을 $s$, $e$라 하고 파란 선의 양 끝점을 $ns$, $ne$라 하자. ①은 $s \leq ns\ \& \ ne \leq e$인 경우이고, 더 작은 선분을 무시하는걸로 해결할 수 있다. ②는 $ns < e$인 경우이고, 두 선분의 길이의 합에 중복된 $e - ns$의 값을 빼줌으로써 해결할 수 있다. ③의 경우엔 그냥 둘 다 더하면 된다. 파란 선은 현재 내가 보고있는 선분, 빨간 선이 파란 선분의 바로 직전 선분이다. 정답 코드 질문, 피드백 환영합니다.