[CF 1169B] Pairs - 1500 문제 설명 : 두 개의 정수로 구성된 pair가 총 m개 주어진다. 임의의 정수 2개(x,y)를 선택해서 최소 하나의 정수가 모든 pair에 등장하게 만들 수 있는지 판단하는 문제이다. 풀이 : 정답이 존재하기 위해서는 m개의 pair중에서 임의의 pair 하나를 선택했을 때 둘 중 하나는 반드시 x,y와 동일할 것이다. 그래서 기본 전제로 pair의 0번째 원소(몇 번째 원소인지는 상관없다) 중 하나에 x,y중 하나는 존재한다는 것을 깔아서 이것이 성립할 수 있는지 검증해볼 것이다. pair의 첫 번째 원소의 first와 second를 각각 x라고 가정하고, 다음과 같은 시행을 한다 : m개의 pair에 대해서 두 정수 모두 x와 같지 않다면 need라는 변수..
[Codeforces 1062B] Math 문제 설명 : 임의의 수 n이 주어졌을 때, 두 가지 종류의 연산을 수행할 수 있다. 하나는 n에다가 임의의 수 x를 곱할 수 있고, 다른 하나는 (현재 n이 제곱수 일 때)루트를 취할 수 있다. 이 두 연산을 사용하여 n을 최대한 작게 만들고, 그 수행 횟수를 구하는 문제이다. 풀이 : 이 문제와 같이 어떤 수가 주어지고, 그 숫자에 연산을 취해서 값이 변해나가는 유형의 문제는 본인이 직접 예시 숫자들을 몇 개 끄적여보면서 규칙성(혹은 최적의 방법)을 찾아나가야 한다.n을 최대한 작게 만드는게 목표이므로 나는 루트를 최대한으로 많이 취해야 할 것이다. 따라서 루트 연산이 가능한 형태로 n을 가공해야 한다. 루트 연산은 소인수들의 지수들이 모두 짝수여야만 가능하..
[Codeforces 1061B] Views Matter Problem - B - Codeforces codeforces.com 문제 설명 : i번째에 a[i]층 만큼 쌓인 블럭들이 주어진다. 제거할 수 있는 블럭의 최대 개수를 구하는데, 제거 하기 전과 후의 위에서 본 모습과 옆에서 본 모습에는 차이가 없어야 한다. 참고로 중력은 고려하지 않아서 아래에 있는 블럭을 제거해도 위에 있는 블럭을 떨어지지 않는다고 가정한다. 풀이 : 일단 오름차순으로 정렬을 한다. 그리고 처음에는 각 블럭들을 1개만 제외하고 나머지 (a[i]-1)개의 블럭을 모두 제거한다고 가정한다( ans+=a[i]-1 ). 여기까지만 생각하면 높이가 1 2 3 4 와 같이 높이가 1씩 차이나는 블럭 배치는 정답을 구할 수 있으나, 1 ..
[Codeforces 1130D2] Toy Train Problem - D2 - Codeforces codeforces.com 문제 설명 : n개의 역이 있는 장난감 기차가 있다. 그리고 이 기차는 m개의 사탕을 옮겨야 한다. 각 사탕에는 출발역과 도착역의 정보가 주어지고 최종 목표는 모든 사탕들을 도착역으로 운반시켜야 한다. 기차에 실을 수 있는 사탕의 개수는 무제한이지만, 한 역에서 기차에 실을 수 있는 사탕은 최대 1개이다. 기차의 출발 지점이 1~n번 역일 때 각 역마다 사탕을 모두 운반하기 위한 최소 이동 횟수를 구하는 문제이다. 풀이 : (이 문제는 쉬운 버전이 있고, 어려운 버전이 있는데 어려운 버전을 기준으로 설명한다. 둘의 차이는 n,m의 크기이다.) 출발역과 도착역을 입력을 받을 때부터..
[Codeforces 1141E] Superhero Battle Problem - E - Codeforces codeforces.com 문제 설명 : 몬스터의 체력과 n명의 플레이어의 공격력이 각각 주어진다. 각 플레이어들은 1번부터 순서대로 몬스터를 공격해서 본인의 공격력만큼 몬스터의 체력을 변화시킬 수 있다(공격력이 음수면 체력을 깎고지만, 양수면 힐을 해준다). 마지막 플레이어까지 모두 공격을 마쳤으면 다시 1번 째 플레이어로 돌아와서 이를 반복한다. 이렇게 해서 몬스터의 체력이 0이하로 만들 수 있는지와, 가능하다면 그 시점은 몇 번째인지를 구하는 문제이다. 풀이 : H의 최대가 10^12(1조)이기 때문에 직접 0이 될 때까지 돌려보는 것은 불가능하다. 플레이어들이 모두 한번씩 공격을 하는데 그..
[Codeforces 1065C] Make It Equal 참 오랫동안 붙잡고 있었던 문제이다. 처음에는 바이너리 서치로 풀려고 해봤는데 시간이 터졌다. 그렇게 어떻게 풀어야 할지 일주일 넘게 고민하다가 결국 솔루션을 봤다. 솔루션은 '지금까지 소모된 cost'(=sum) + '현재 높이에서 새롭게 추가된 막대의 수'(=cnt[i])의 총합을 계산해서 k이하일 때는 계속 sum에 누적해나가고, k를 초과했다면 slice수를 추가하고, sum=cnt[i-1]로 두면 된다. 그리고 다음 높이(i-1)에서 소모되는 cost는 cnt[i-1]+=cnt[i]로 구할 수 있다.문제의 첫 번째 예시 입력처럼 1 2 2 3 4 가 있다고 가정해보자. 가장 높이가 높은 4부터 시작해서 그 다음 높이인 3에 도달했다고 하..
[Codeforces 1118B] Tanya and Candies n일동안 하루마다 할당된 캔디의 수가 주어진다. 이때 어떤 하루의 캔디를 모두 삭제 한 뒤의 상태(그 이후의 날은 앞으로 한 칸씩 당겨짐)에서 홀수 날 캔디의 합과 짝수 날 캔디의 합이 같은 날이 n일 중에 몇 일인지 찾는 문제이다. naive하게 푼다면 i번째 날을 계산하기 위해서 1~(i-1)번 째까지 수 + (i+1)~n번 째까지의 캔디를 모두 더하면 되고, 이 풀이는 O(N^2)이다. 하지만 이 문제는 n이 최대 20만이기 때문에 시간이 초과될 것이다. 그래서 관건은 1~(i-1)번째까지, (i+1)~n번 째까지의 캔디의 합을 빨리 구해야한다. 당연하게도 Prefix Sum(부분합)으로 푸는 문제이다. 이 문제에서 한 가지 처리해주..
15668-방 번호 아이디어성이 짙은 문제이다. N=10억이기 때문에 당연히 전탐색은 불가능하다. 그래서 반드시 N을 다 보지 않고도 풀 수 있는 방법이 있을 것이라고 생각했다. 풀이를 말로 설명하기는 참 어려운 문제이다.결론부터 얘기하자면, 단 43210까지만 봐도 모든 경우를 처리할 수 있다. i=1~43210까지의 반복문에서 i와 N-i 의 값을 구해서 그 두 값에서 겹치는 수가 있는지만 확인해주면 된다. 예를 들어, N=100 일 때를 생각해보자. i=1 때는 N-i(=k라고 하자)=99가 되고 k 자체에서 9가 두 번 사용되므로 탈락이다. i=2 때는 k=98이고 모든 수가 한 번 씩만 사용되었으므로 가능하다. 그래서 i=1~43210까지 하나라도 가능한 케이스가 있다면 출력하고, 모두 불가능하..