Problem Solving/문제풀이 (89) 썸네일형 리스트형 백준 17955번 Max or Min 어제 처음으로 팀연습하다가 다이아 3을 풀어서 기쁜 마음에 풀이를 작성한다. 심지어 제출 한 번만에 맞췄다! 문제 요약 길이가 $N$인 원형 수열 $a$가 주어진다. $1 \le a_i \le M$ 이다. 이 때 다음과 같은 연산을 할 수 있다. $a_i$를 하나 골라서 인접한 두 수와 $a_i$의 최솟값 혹은 최댓값으로 $a_i$를 바꿔줄 수 있다. 이런 연산을 반복해서 수열 전체를 $k$로 만들기 위한 최소 연산 횟수를 계산해야 한다. $3 \le N \le 2 \cdot 10^5, 1 \le M \le 10^5$ 풀이 실제로 구해야 하는 것은 $1 \le k \le M$인 모든 $k$에 대한 답이지만 일단 이걸 $k$로 고정한 뒤에 최적의 연산 횟수를 구해보자. 일단 $k$가 존재하지 않는 수라면 .. 백준 21916번 Neo-Robin Hood 문제 요약 돈을 $m_i$달러만큼 들고 있는 정치가 $N$명이 주어진다. 각 정치가는 $p_i$만큼 돈을 원하고 있다. 이 때, 정치가들한테서 돈을 훔치려고 하는데 그냥 쌩으로 훔치면 위험하기 때문에 훔친사람의 수와 같은 수의 정치가들한테 그들이 원하는 만큼의 돈을 줘야 한다. 이 때, 돈을 훔칠 수 있는 정치가의 수의 최댓값을 구하시오. $ N \le 100,000$ $1 \le m_i, p_i \le 10^9$ 풀이 관찰 1 : 일단 돈을 줄 사람 $k$ 명을 정했다고 하자. 그렇게 되면 돈을 훔쳐야 될 사람 $k$ 명은 남은 사람 중에서 돈이 제일 많은 $k$ 명이 되는 것은 자명하다. 관찰 2. $k$ 명에게서 훔치는 것이 가능하다면 당연히 $k$ 명보다 적은 수의 정치가에게서 훔치는 것도 가능하.. 백준 15339번 Counting Cycles 문제 요약 정점이 $N$개 있고 간선이 $M$개인 연결그래프가 주어진다. 이 때, 단순 사이클의 갯수를 구해야 한다. $ 3 \le N \le 100000$, $ N-1 \le M \le N+15$ 풀이 제한이 10만이었구나 왜 20만으로 착각했을까 일단 간선의 제한이 매우 수상하다. $N+15$라는 저 어정쩡한 제한을 보라. 일단 간선이 $N-1$일 때는 트리다. 사이클이 존재하지 않는 그래프고, $N$개일 때는 당연히 사이클은 하나다. 트리에서 간선이 하나 추가될 때 마다 사이클이 생겨난다. 즉, 이렇게 해서 생길 수 있는 사이클은 최대 16개다. 여기서 중요한 사실이 있는데 생길 수 있는 사이클은 사이클끼리 겹치게 해서 홀수번만 겹쳐진 간선들을 사용하는 사이클 외에는 존재 할 수 없다. 는 강한 추.. 백준 18214번 Reordering the Documents 문제 요약 크기가 $N$인 문서 더미가 주어진다. 각 문서에는 $1$부터 $N$까지 수가 부여되어 있다. 문서 더미는 스택과 같은데 놓여있는 문서들의 순서는 뒤죽박죽이다. 이 때, 이 문서들을 다른 두 개의 임시 문서 더미로 옮긴 뒤에 정리하는 방식으로 문서 더미의 위에서부터 $1$부터 $N$까지로 차례대로 놓여있는 문서 더미를 만들려고 한다. 임시 문서 더미들은 최대 $M$의 높이를 가질 수 있다. 이 때, 서로 다른 두 개의 임시 문서 더미에 문서들을 놓는 경우의 수를 구하여라 . $ 1 \le N \le 5000$, $ N/2 \le M \le N$ 문제 요약이 잘 안된다. 링크 풀이 일단 처음의 문서 더미의 위에서부터 아래로 내려가는 순으로 문서들의 번호가 주어진다. 그리고 서로 다른 두 개의 스.. 백준 15326번 Usmjeri 문제 요약 크기가 $N$인 트리가 주어진다. 이러한 트리에서 간선들에 방향을 부여하려고 한다. 이 때, $(u, v)$ 쌍이 $M$개 주어지는데 이는 간선들에 방향을 부여했을 때 $u \rightarrow v$인 경로가 존재하거나 $u \leftarrow v$인 경로가 존재해야 한다는 뜻이다. 문제에서 원하는 것은 $M$개의 조건을 만족하면서 간선에 방향을 부여하는 방법의 수를 구하는 것이다. $ 1 \le N, M \le 3 \cdot 10^5 $ 풀이 $(u, v)$가 주어지면 만족해야 하는 조건은 세가지가 생기는 것으로 볼 수 있다. $LCA(u, v)=l$이라고 하자. $u \rightarrow l$의 간선들은 방향이 같아야 한다. $l \rightarrow v$의 간선들은 방향이 같아야 한다. .. 백준 20349번 Xortest Path 문제 요약 정점 수가 $n$이고 간선 수가 $m$인 그래프가 주어진다. 어떤 경로의 거리는 해당 결로에 속하는 간선들의 XOR로 정의한다. 이 때, 쿼리가 $q$개 주어지는데 두 정점의 번호가 주어진다. 두 정점간의 경로 중에서 최단거리를 가지는 경로의 거리를 출력하시오. $ 1 \le n \le 10^4 $, $ n-1 \le m \le 10^5$, $ 1 \le q \le 10^5$, 각 간선의 가중치는 최대 $10^{18}$이다. 풀이 두 정점이 주어지면 두 정점간의 최단 경로를 찾아야 한다. 일반적으로 그래프에서 이는 매우 어렵다. 그런데 이런 문제를 냈다는 것은 XOR로 정의한 새로운 거리가 무슨 특성을 갖고 있기에 냈을 것이다. 일단 그래프가 connected라는 조건을 줬으니 트리에서 생각을.. 백준 20226번 Luggage 문제 요약 숫자 $p$가 주어진다. $p=whd$로 나타낼 수 있는 $(w, h, d)$중에서 $w+h+d$의 값이 최소가 되는 $(w,h,d)$의 $w+h+d$를 출력하시오. 주어지는 테스트케이스의 최대 숫자는 300개이며 $p \le 10^{15}$이다. 풀이 가장 간편한 소인수분해인 $O(\sqrt{N})$짜리 소인수분해 방법으론 대략 3000만 곱하기 300으로 시간초과를 받을거 같다. 그래서 소인수분해 하려면 더 빠른 방법을 써야만 한다. 나는 폴라드 로를 사용했다. 이제 $p$를 소인수 분해해서 $p$의 약수를 전부 만들어준다. 약수가 제일 많은 수라고 해봤자 3만개를 넘지 않는다. 이제 이 약수들 중에서 하나를 고정한 다음에 나머지 숫자들을 찾아보도록 하자. 고정하는 수는 $d$로 하자. $.. 백준 18216번 Ambiguous Encoding 문제 요약 0과 1로 이루어진 문자열 $n$개가 주어진다. 이런 문자열들 중에서 적당히 골라서 이어 붙인 문자열을 $s$라고 하자. 이 때, 주어진 문자열 $n$개를 이용해서 $s$를 분할하는 방법이 두 가지 이상이라면 $s$를 ambiguous하다고 한다. 만들 수 있는 ambiguous한 문자열 중에서 가장 길이가 짧은 것의 길이를 출력하시오. 만약 만들 수 없다면 0을 출력하시오. 주어지는 $n$개의 문자열의 길이는 16 이하이다. $ 1 \le n \le 1000 $ 풀이 예제를 살펴보자. 주어진 문자열이 0, 01, 10인데 010은 0, 10 혹은 01, 0으로 분할될 수 있다. 따라서 010은 ambiguous한 문자열이고 이게 제일 짧은 경우이다. ambiguous한 문자열이 되기 위해서는.. 이전 1 2 3 4 ··· 12 다음