데구리 블로그

문제 링크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$의 값을 빼줌으로써 해결할 수 있다. ③의 경우엔 그냥 둘 다 더하면 된다. 파란 선은 현재 내가 보고있는 선분, 빨간 선이 파란 선분의 바로 직전 선분이다. 정답 코드 질문, 피드백 환영합니다.

문제 링크 https://www.acmicpc.net/problem/15921 힌트에 괜히 쓸데없는 말을 집어넣어서 평균과 기댓값을 구하도록 유도하는데 굳이 그럴 필요 없다. 기댓값 $E(X) = \sum\nolimits_{i}p_ix_i$이고 어떤 수 x가 수열에 등장할 확률 $P(x) = \dfrac{\text{x의 등장 횟수}}{\text{전체 수열의 길이}}$ 이다. x의 등장 횟수를 $c$라 하고 전체 수열의 길이를 $n$이라 하면 $P(x) = \dfrac{c}{n}$ 이고 이때 $px = \dfrac{cx}{n}$인데, 이는 $\dfrac{x}{n}$ 을 $c$번 더한 것과 같다. 결국 기댓값 $E(X) = \sum\nolimits_{i}\frac{x_i}{n}$이므로 평균과 다를 바 없기 ..

문제 링크 https://www.acmicpc.net/problem/15920 단순 구현? 시뮬레이션? 문제다. state를 정의하자 state == 0 일때 마네킹 5개가 날아가고 state == 1 일때 마네킹 1개가 날아가고 state == 2 일때 마네킹 6개가 모두 날아가는 걸로 하자. P가 나올때마다 state의 상태를 0 ~ 1 사이에서 반전시키는데, W가 한 번 나온 상황에서 P가 나온다면 state를 2로 고정시키자. W가 2번 나왔을 때 답을 출력하고 종료하자. 정답 코드 질문, 피드백 환영합니다.

문제 링크 https://www.acmicpc.net/problem/15918 언뜻보면 어려워 보이지만 n의 범위가 작기때문에 백트래킹으로 가능한 자리에 하나하나 다 넣어보면 쉽게 풀린다. 비어있는 i번째 자리에 어떤 수 num을 넣고 싶으면 (i+num+1)번째 자리가 비어있는지 확인하면 된다. 시간복잡도는 대충 O((N-2)!)인데 불가능한 자리가 많으므로 저거보다 훨씬 덜 나온다. 정답 코드 질문, 피드백 환영합니다.

문제 링크https://www.acmicpc.net/problem/15917 어떤 수 a가 2의 거듭제곱꼴인지 판별하면 된다.쿼리의 수 Q가 $1 \leq Q \leq 1,000,000$이므로 단순히 a의 비트를 순회하며 1이 하나인지 확인해도 $O(32Q)$이므로 충분하다.좀 더 효율적으로 하고싶다면 $a\ \&\ (a - 1)$이 0인지 확인하자.모든 양수 a에 대해 a가 2의 거듭제곱꼴이라면 위의 값이 0이 나온다. 글을 쓰면서 문제를 다시 확인했는데 힌트 부분에 이미 답이 나와있었다... 닉값하는 문제;; 정답 코드 질문, 피드백 환영합니다.

문제 링크https://www.acmicpc.net/problem/15916 평면 위의 점들을 이은 그래프와 한 직선 $y = kx$가 주어졌을 때 $(0, 0)$이외의 점에서 한 번이라도 직선과 그래프가 만나는지를 확인하면 된다. CCW를 이용해 선분의 교차를 확인하자. 우선 직선과 선분의 교차 여부를 판단하기는 어려우니, 선분과 선분의 교차 여부를 확인하기 위해 $y = kx$를 선분으로 만든다. 평면 위 점들의 y좌표가 $0 \leq y \leq 2^{30}$ 이므로 직선 위의 점 중 $y' > 2^{30}$ 를 만족하는 적당한 점$(x',\ y')$와 $(0, 0)$을 이어 선분으로 만들면 된다. $x' = \dfrac{2^{31}}{k}$ $y' = kx'$ 정도가 좋겠다.수학적 나눗셈이 아닌 ..