본문 바로가기

Problem Solving/문제풀이

(41)
[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$일때만 해결하면 그 아래는 쉽게 해결할 수 있으므로 이 경우에 대..
[ICPC] Latin America Regional 2017 일부 문제 풀이 A. Arranging Tiles BOJ 15052번: https://www.acmicpc.net/problem/15052 이 문제의 핵심은, 어떤 2개의 다각형을 얼마나 가까이 붙일 수 있는 지 빠르게 계산하는 것입니다. 다각형을 배열하는 순서를 정하고, 그 다각형들에 대해 한 다각형의 x좌표 최댓값이 바로 다음 다각형의 x좌표 최솟값과 같게 배치했다고 합시다. 그렇다면 이 때의 해는 모든 다각형의 x축 길이 합에서, 모든 인접한 다각형 쌍에 대해서 다각형을 얼마나 가까이 이동시킬 수 있는지의 합을 뺀 것이 됩니다. 따라서 우리는 다각형 쌍이 주어졌을 때 이를 서로 붙일 수 있는 최대 길이를 미리 계산해 둔 뒤 가능한 모든 배열에 대해 해 중 최소를 찾아주면 됩니다. 붙일 수 있는 최대 길이를 모두 전..
[BOJ] 15404 Divide and Conquer 문제 요약 $N$개의 정점이 있고, 이 정점을 잇는 스패닝 트리가 2개 있다. 이 두 스패닝 트리의 합집합으로 구성되는 그래프에 대해(간선은 구별된다), $K$개의 간선을 제거하면 그래프를 연결 그래프가 아니도록 할 수 있다. 이 때 $K$의 최솟값을 구하고, 그 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력하면 된다. 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $K=2$이거나, $K=3$. 증명은 다음과 같다. 임의의 정점에 연결된 모든 간선을 제거하면 그 정점은 다른 정점과 연결되어 있지 않기에, 그래프는 연결 그래프가 아니다. 따라서 $K$는 모든 정점의 degree 중 최솟값보다 클 수 없다. 간선 하나는 정확히 두 개의 정점의 degree를 1만큼 증가시키므로, 모든 정점의 d..
[BOJ] 16910 mex와 쿼리 [문제 링크](https://www.acmicpc.net/problem/16910) 문제 요약 다음과 같은 세 쿼리를 처리해야 합니다. [l,r]에 속하는 모든 자연수를 배열 A에 추가한다. 이미 있는 수는 무시된다. [l,r]에 속하는 모든 자연수를 배열 A에서 제거한다. 없는 수는 무시된다. [l,r]에 속하는 모든 자연수에 대해 있으면 제거, 없으면 추가한다. 각 쿼리를 수행 한 뒤에 이 배열에 없는 수 중 가장 작은 자연수를 찾으면 됩니다. 문제 풀이 일단 문제에서 요구하는 좌표가 크니 좌표 압축을 시도하고 생각합시다. 그 이후 Lazy Propagation 달려 있는 세그로 연산을 처리해주며 특정 구간에 존재하는 수의 개수를 세 주면 됩니다. Lazy 연산 중에 1번 쿼리와 2번 쿼리는 서로 상..
[BOJ] 14591 KUBC League, 17165 Gosu 14591 KUBC League 문제 요약 토너먼트 그래프가 있다. 1번 정점에서 시작해서 모든 정점을 순회하는 단순 경로를 찾으면 된다. 문제 풀이 DFS 스패닝 트리에 의거하여, 그냥 DFS를 1번 정점에서부터 수행 후 마지막부터 출력해주면 된다! 코드 #include #include #include #define all(x) (x).begin(), (x).end() #define endl "\n" #define ends " " #define pb(x) push_back(x) #define fio() ios_base::sync_with_stdio(0); cin.tie(0) using namespace std; typedef long long ll; typedef pair pii; typedef pai..