본문 바로가기

Problem Solving/문제풀이

 (45)
[BOJ] 24973 Up Down Subsequence 문제 요약 길이가 $N$인 수열이 주어진다. 어떤 부분수열을 앞에서부터 읽었을 때 인접한 두 수가 커지면 U, 작아지면 D를 적은 문자열이 있다고 하자. 문자열 $S$가 주어질 때 부분수열을 잘 골라서 만든 문자열과 $S$의 common prefix 길이를 최대화하여라. 문제 풀이 결론부터 말하면, 다음을 반복하면 된다. 1. 문자열을 (연속한 문자 종류, 개수)로 압축한다. 2. 맨 앞이 U면 LIS, D면 LDS를 길이가 그 문자의 개수가 될 때까지 찾는다. 3-1. 만약 찾지 못한다면 LIS나 LDS의 길이(정확히는 길이-1)만큼 추가로 문자를 처리할 수 있고 그 뒤는 불가능하다. 3-2. 만약 찾는다면 연속한 문자를 모두 처리할 수 있다. LIS/LDS의 마지막 위치가 pos라고 하자. 그러면 계..
[BOJ] 23172 Equivalent Pipeline 문제 링크: [BOJ 23172](https://www.acmicpc.net/problem/23172) 문제 요약 정점이 $n$개인 가중치 있는 트리가 $d$개 있다. $vT(i,j)$를 $T$에서 $i$와 $j$를 잇는 최단경로 중 가중치의 최솟값이라고 하자. 만약 모든 $i$, $j$ 쌍에 대해 이 값이 같다면 두 트리는 동치이다. 동치 관계를 구하여라. 풀이 트리에서 가장 가중치가 작은 간선들을 생각해보자. 이 간선들을 제거하면, 트리가 여러 컴포넌트로 쪼개질 것이다. 이때 같은 컴포넌트에 있는 정점들끼리의 $vT(i,j)$ 값은 반드시 최소 가중치보다 크고, 다른 컴포넌트에 있는 정점들끼리의 값은 정확히 최소 가중치일 것이다. 따라서 두 트리가 동치이려면 최소 가중치 간선들을 기준으로 쪼갰을 때 ..
[BOJ] 16711 Erasing Matrix 문제 링크: [BOJ 16711](https://www.acmicpc.net/problem/16711) 문제 요약 격자가 있다. 격자에서 인접한 두 수를 골라 임의의 수를 더할 수 있다. 격자 안의 수가 항상 음수가 되지 않게 하면서 최종적으로 모든 수가 0이 되게 하는 방법을 찾아라. 풀이 일단 가장 먼저 생각해봐야 할 점은 -1을 찍을 조건이다. 이런 식으로 격자에서 인접한 두 수를 고려하는 문제는 특성상 체스판처럼 색칠하면 이분 그래프 구조가 나오는데, 이를 활용해 볼 수 있다. 인접한 두 수에 어떤 수를 더하더라도 (흰 칸의 수 합) - (검은 칸의 수 합)은 변하지 않으므로, 이 두 값은 반드시 같아야 한다. 만약 이 값이 같다면 항상 0으로 만들 수 있을까? 가능하다. 핵심은 같은 색깔이라면 ..
[BOJ] 17434 도로 청소 문제 링크: [BOJ 17434](https://www.acmicpc.net/problem/17434) 문제 요약 무방향 그래프가 있다. 교집합이 없고 방문하는 간선의 합집합이 그래프 간선 전체인 오일러 투어 2개를 구하여라. 풀이 풀이 방향을 잘못 잡으면 구데기같은 구현에 고통받게 된다. 일단 가장 먼저 생각해야 하는 건, 그래프의 홀수 차수 점 개수는 반드시 0, 2, 4중 하나여야한다는 것이다. 오일러 투어를 하나 구하고 그 간선들을 모두 제거한다고 생각해보자. 그러면 오일러 순환인 경우 홀수 차수 점 개수는 그대로고 아니라면 2개 줄어든다. 모두 지웠을 때 개수가 0이어야 하므로 이 셋 중 하나이다. 홀수점 0개 아무 오일러 순환을 하나 찾자. 그 뒤 아무데서나 적당히 끊어서 오일러 투어 2개로 ..
[BOJ] 19677 Holy cow, Vim! (Hard) 문제 설명 생략한다. 문제 접근 이 문제를 풀기 위해서는 굉장히 많은 시행착오를 거쳐야 한다. 아래는 그 시행착오를 줄이기 위한 접근들을 단계별로 서술해놓았다. 그러나 이를 보지 않고 많은 시행착오를 겪는 것이 거의 모든 측면에서 도움이 될 것으로 보인다. 일단 lexicographical하게 정렬했을 때 명령어의 순서는 '*', '+', '-', '/', 'dup', 'input', 'jump', 'pop', 'print', 'push' 순서이다. 문제는 이 중 사칙연산과 dup은 우선순위도 빠르면서 스택에 필수적으로 하나 이상의 원소를 요구하기에, 두 명령어 ..
USACO 2020 Open contest Gold 풀이 Intro PS를 거의 한달간 접었었는데, 올해 ICPC를 나갈 수 있다는 희망이 보여서 급하게 PS 재활 중입니다. 최대한 빨리 플래티넘을 안정적으로 해결할 수 있는 실력까지 올렸으면 좋겠네요. 가능할지는 아직 미지수입니다. 이 셋 푸는데도 두시간은 넘게 걸렸으니 미래가 어둡네요 :( 18874 Haircut 문제 링크 : https://www.acmicpc.net/problem/18874 문제를 요약하면 각 $j$에 대해 $j$보다 큰 수열의 원소들이 정확히 $j$로 바뀔 때, 수열의 inversion을 구하는 문제입니다. 이런 문제에서 흔히 나오듯이 $j$를 큰 수부터 작은 수까지 움직이면서 차례대로 구해봅시다. 수열의 inversion은 수열의 각 원소 $a_i$에 대해 인덱스가 $i$보다 작으면..
Random Problem Solving 1 Intro 정말 PS를 하고 싶었기 때문에, 몇 문제를 풀었다. 잘 푼 문제도 있고 그렇지 못한 문제도 있지만, 어쨌던 간에 풀었던 문제들의 기록을 간단하게나마 남길까 한다. 20045 Trading System 먼저 다음과 같은 값을 찾는다. 구간합이 $x$ 이상인 구간의 개수가 $k$ 이상인 가장 큰 $x$ 이 값을 찾아야 하는 이유는, 이 값을 찾는다면 실제 수열은 $x+1$ 이상인 구간합을 모두 set을 이용해서 찾아 준 다음 나머지를 $x$로 채우는 방식으로 역추적해낼 수 있기 때문이다. 따라서 이 값을 찾는 것이 답을 구하는 것과 동치이고, 이 정도 문제를 해결할 수준이라면 이 과정은 매우 쉬우므로 설명은 생략할 것이다. 이 값은 $x$에 대한 Parametric Search로 찾아줄 수 있다..
[BOJ] 17524 Dryer 문제 링크 : www.acmicpc.net/problem/17524 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $t_i$가 같은 옷이 2개 있다면 어차피 $w_i$가 큰 쪽이 더 오래 걸릴 것이기 때문에, 같이 넣고 말려도 무방하다. 따라서 의미 있는 옷은 각 $t_i$에 대해서 유일하므로, $1\le N\le61$과 사실상 같다. 그 다음으로 해야 하는 관찰들은 다음과 같다. 어떤 옷들의 집합을 같은 건조기에 넣고 돌린다면, 그 건조기의 온도는 반드시 옷 중 $t_i$의 최솟값과 같아야 한다. 이는 매우 자명하다. 어떤 건조기가 이미 $x$초 동안 돌아간다면, $x$초 이하를 소모하는 다른 옷을 끼워 넣어도 상관없다. $k=3$일때만 해결하면 그 아래는 쉽게 해결할 수 있으므로 이 경우에 대..

티스토리툴바