[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 1138D] Camp Schedule Problem - D - Codeforces codeforces.com 문제 설명 : 0과 1로만 구성된 문자열 s와 t가 주어진다. 목표는 문자열 s에 등장하는 0과 1의 빈도수와 동일하게 문자열을 변형시키는 것인데 그 문자열의 substring으로 문자열t가 최대한 많이 등장하도록 변형시켜야 한다. 풀이 : 조건에서 문자열 t를 최대한 많이 등장하도록 해야 한다. 여기서 substring은 겹치는 것이 가능하다. 예를 들어서 문자열 "aaa"가 있고 패턴이 "aa"라면 총 2개의 substring이 존재하는 것이다. 따라서 나는 우선 문자열 t에서 최장 길이의 공통 prefix와 suffix를 찾아야 한다. 공통부분을 찾으면 현재의 suffi..
[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 1082C]Multi-Subject Competition 문제 설명 : 여러 명의 학생들이 대회에 참가하려고 한다. 대회에는 총 m가지의 종목이 있다. 입력으로 각 학생들이 할 수 있는 종목의 종류와, 그 종목에서의 능력치가 주어진다. 각 종목에 참가하는 학생의 수는 모두 동일해야한다고 할 때, 참가하는 학생들의 능력치의 합이 최대가 되도록 하는 문제이다. 풀이 : 풀이가 엄청 간단한 문제인데 왜 이렇게 어렵게 생각했나 싶은 문제이다. 우선 2차원 벡터를 선언해서 각 종목별로 학생들의 능력치를 저장한 다음 각 종목 별로 능력치 순으로 내림차순 정렬을 한다. 그리고 sum[]이라는 배열에다가 현재 종목의 누적합이 0이상일 때만 더해준다. 이 과정이 끝나면 sum배열의 1~n번까지의 인..
[Codeforces 1082B] Vova and Trophies 문제 설명 : n개의 'G'또는 'S'로만 이루어진 문자열이 주어진다. 여기서 연속된 'G'로만 이루어진 substring의 최대 길이를 구해야 하는데, 최대 한 번 문자열에서 아무 두 인덱스를 골라서 문자를 swap하는 것이 허용된다. 풀이 : swap하는 조건이 없다면 단순히 연속된 문자열의 개수가 몇 개인지 세면 될 것이다. 그런데 swap 조건이 끼어들어서 문제가 조금 까다로워졌다. 예를 들어서 문자열 "GGSGSG"가 있을 때 swap이 없다면 최대 길이는 2 지만, swap을 한다면 3번 째(S)와 6번 째(G)를 swap하면 최종적으로 "GGGGSS"가 되어서 최대 길이는 4가 된다. 이처럼 swap조건이 있을 때는 연속된 '..
[Codeforces 1140C]Playlist 문제 설명 : n개의 노래의 length와 beauty가 각각 주어진다. 나는 여기서 최대 k개의 노래를 선택해서 pleasure가 최대가 되도록 해야 하는데, pleasure를 계산하는 공식은 (선택한 노래들의 length들의 합)*(선택한 노래들 중에서 beauty가 가장 작은 값)으로 계산된다. 풀이 : 우선 beauty를 오름차순으로 정렬한다. 정렬을 하는 이유는 값을 크기 순으로 배치하여 한쪽 방향으로 순회함으로써 하한(lower bound)을 고정할 수 있기 때문이다. 문제에서 pleasure를 계산할 때 어차피 beauty가 가장 작은 값이 무엇인지만 중요하므로, 가장 작은 값을 미리 정해놓음으로써 나머지 노래들은 무조건 그 보다 beauty가..
[Codeforces 1136C] Nastya Is Transposing Matrices 문제 설명 : ( n x m ) 크기의 행렬 A, B가 주어진다. 여기서 A행렬 안에 속하는 부행렬(sub-matrix)를 임의로 선택하여 Transpose 연산을 수행할 수 있다. 여기서 부행렬의 크기는 반드시 정사각행렬이어야 한다. Transpose 연산을 무제한으로 많이 수행할 수 있다고 할 때 A행렬이 B연산으로 바꾸는 것이 가능한지를 묻는 문제이다. 풀이 :일단 행렬의 Transpose 연산의 특성상 대각선 성분에는 변화가 없고, 그 외에 성분들만 서로 위치를 바꾸게 된다. sub matrix의 크기를 마음대로 설정할 수 있으므로, '행'+'열'을 만족하는 대각성 성분들끼리는 자리를 바꾸는 모든 경우의 수가..