문제 링크 15922 아우으 우아으이야!! 문제와 같은 문제입니다. 예전에 썼던 풀이 그대로 퍼올게여. 문제를 풀기 위해 수직선들을 좌표가 낮은 순으로 정렬하자. 그리고 앞의 수직선부터 탐색한다. 인접한 두 수직선의 관계는 다음과 같다. 빨간 선의 양 끝점을 $s, e$라 하고, 파란 선의 양 끝점을 $ns, ne$라 하자. ①은 $s \leq ns$ & $ne \leq e$인 경우이고, 더 작은 선분을 무시하는걸로 해결할 수 있다. ②는 $ns < e$인 경우이고, 중복해서 더해지는 $e - ns$값을 빼주면 된다. ③의 경우엔 그냥 둘 다 더하면 된다. 파란 선은 현재 내가 보고있는 선분, 빨간 선이 파란 선분의 바로 직전 선분이다. 정답 코드
문제 링크 기억하는 알파벳이 판별할 문자열에 순서대로 들어있는지 확인하면 된다. 비슷한 문제로 15904 UCPC는 무엇의 약자일까? 가 있다. 기억하는 알파벳의 문자열을 $s$라 하고 판별해야 하는 문자열을 $x$라 하자.$s$는 별개의 인덱스 $idx$를 가지고, $x$를 순서대로 탐색하면서 $s[idx] = x[i]$이면 $idx$를 증가시킨다.$idx$가 $s$의 끝까지 간다면 모두 나온 것이니 "true"를 출력하고, 그렇지 않으면 "false"를 출력한다. 정답 코드 질문 및 피드백 환영합니다.
문제 링크 14268 내리갈굼 문제와 15782 Calculate! 2 문제와 같은 유형이다.자세한 풀이는 링크를 들어가면 있다. 두개 다 보면 이해 간다. 세그먼트 트리를 이용하긴 하지만 쿼리는 구간이 아닌 한 정점에서만 물어보므로 lazy propagation을 단순히 O(lgN)의 시간복잡도로 해결하기 위해 사용한다.따라서 세그먼트 트리에서 리프노드 이외의 노드의 값은 뭐가 들어있던 상관이 없기 때문에 코드의 29, 41번째 줄에서 v를 한 번만 더해줬다(리프노드에선 원래 한 번만 더해진다). 크게 상관있는 부분은 아니다. 정답 코드 질문 및 피드백 환영합니다.
문제 링크 트리의 한 노드가 갈굼당하면 그 자식들이 모두 갈굼당해야한다. 구간이 보인다. 트리를 평평하게 펴서 세그먼트 트리로 만들고, lazy propagation을 적용하자.비슷한 문제로 15782 Calculate! 2 가 있다. 트리를 펴는 자세한 설명은 해당 링크를 보자. 위 링크와 차이점은 이번에는 pre-order로 순회했다는 것이다. 두 배열 $l$과 $r$, 주어진 트리의 어떤 정점 x에 대해 $l[x]$는 세그먼트 트리에서 x의 시작 구간이고 $r[x]$는 끝 구간이다. 이를 dfs로 쉽게 구할 수 있다.$l[x]$는 순회하는 순서로 값을 채워넣으면 된다.$r[x]$는 모든 자식들을 순회한 뒤 $l[x]$에서 자식 수만큼 증가시켜 넣어준다. (이는 세그먼트 트리에서 x의 마지막 자식의 ..
문제 링크 https://www.acmicpc.net/problem/15923 문제가 너무 쉬워서 설명할 게 없다. 방금 받은 좌표를 nx, ny라 하고 직전에 받은 좌표를 x, y라 하면 ans += abs(x+y-nx-ny) 이다. 내용이 너무 없으니 입출력 조건이라도 쓰자. 입력첫째 줄에 꼭지점의 개수 N이 주어진다. (4 ≤ N ≤ 20) 이후 둘째 줄 부터 N개의 줄에 걸쳐 꼭지점의 좌표 (x, y)가 주어진다. 좌표는 40 이하의 음이 아닌 정수이며, 중복되는 좌표는 주어지지 않는다.출력욱제가 설계한 건물의 둘레의 길이를 출력한다. 정답 코드
문제 링크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으로 바꿀지 ..