4Legs_Archives

문제 링크 : www.acmicpc.net/problem/20121 20121번: 카드 셔플 i번째 줄에는 i번째 테스트 케이스의 최소 횟수로 셔플하는 방법을 나타내는 문자열 S = s1s2 ... sK (sj = 'X' or 'Y') 를 출력한다. sj는 j번째 셔플이 X-셔플인지 Y-셔플인지를 의미한다. 방법이 여러 가 www.acmicpc.net 위치가 K인 카드의 X셔플 후 위치는 다음과 같다. 위치가 K인 카드의 Y셔플 후 위치는 다음과 같다. 이를 통해, 같은 위치에서 Y셔플을 한 후의 위치는 항상 X셔플 후 위치의 한 칸 뒤임을 알 수 있다. (단, X셔플 후 위치가 맨 끝일 경우 Y셔플 후 위치는 맨 처음이 된다.) 이제 예제에서 처음 6번 카드에 대해 각 셔플 후 경우를 직접 찾아보자. ..

문제 링크 : www.acmicpc.net/problem/20120 20120번: 호반우와 리듬게임 호반우가 모든 노트를 처리하면 3×1 + 4×2 + (-7)×3 + 1×4 = -6 점을 얻을 수 있습니다. 3번 노트를 제외한 모든 노트를 처리하면 3×1 + 4×2 + 1×1 = 12 점을 얻을 수 있습니다. 3번 노트를 놓쳤기에 4번 노 www.acmicpc.net DP문제의 대표유형인 계단오르기 문제와 유사한 문제이다. 각 노트를 처리하는 것과 계단을 한 번 오르는 것을 동일하게 생각한다면 수월하게 문제를 해결할 수 있다. 단 점수를 계산하기 위해선 현재까지 몇 콤보로 현재 노트를 처리하는지에 대한 정보가 필요하므로, 이 풀이에서는 dp 배열을 2차원으로 두었다. k번 노트를 c 콤보에서 처리한 경..

문제 링크 : www.acmicpc.net/problem/20119 20119번: 클레어와 물약 첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다. 다음 M개의 줄에는 각각의 줄마다 레시피의 정보 k www.acmicpc.net 문제에서 주어진 레시피는, 한 물약을 만들기 위해 필요한 물약에 대한 정보이다. 즉, 레시피의 왼쪽에 있는 물약들을 모두 가지고 있어야 오른쪽의 물약을 만들 수 있다. 이는 곧 하나의 물약을 만들기 위해서는 다른 물약의 제조가 선행되어야 함을 의미하며, 따라서 이 문제를 위상 정렬 문제로 접근할 수 있다. 위상 정렬 (Topological Sort) 위상 정렬..

문제 링크 : www.acmicpc.net/problem/20117 20117번: 호반우 상인의 이상한 품질 계산법 어떤 묶음에 있는 호반우의 품질이 [1, 2, 3, 4] 라고 하면 중간값인 3으로 모든 호반우의 품질을 계산한다. 따라서 이 묶음의 총 가격은 3 × 4 = 12 가 된다. 품질이 [6, 3, 9] 라고 하면 중간값인 6으로 www.acmicpc.net 그리디 알고리즘으로 해결할 수 있는 문제이다. 판매하는 물건들을 가장 비싸게 팔 수 있는 가장 좋은 방법은 가장 싼 물건과, 가장 비싼 물건을 묶어 파는 것이다. 문제에서 물건의 묶음이 짝수인 경우, 가격의 중앙값은 (묶음 개수/2+1)번째 호반우로 정의했기 때문에 (k1, k2) 묶음에 대해서 반드시 k2의 가격이 중앙값이 된다. 따라서..

문제 링크 : www.acmicpc.net/problem/20116 20116번: 상자의 균형 3번 박스의 중심의 x좌표는 9이며 2번 박스의 구간 (0, 20) 에 속한다. 그리고 2, 3번 박스의 중심의 x좌표는 (10+9)/2 = 9.5 이고 1번 박스의 구간 (-10, 10) 에 속하므로 균형을 이룬다. www.acmicpc.net 누적합 등으로 쌓여 있는 상자들의 평균 중심을 구해가며 안정적인 구조인지 판단하면 된다. 이 풀이에서는 맨 위 상자부터 계산하였다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46..

문제 링크 : www.acmicpc.net/problem/20115 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 그리디 알고리즘으로 해결할 수 있는 문제이다. 최종적으로 만든 드링크의 양이 최대가 되기 위해서는, 두 드링크를 섞을 때 버려지는 양이 최소가 되어야 한다. 그러기 위해서는 두 드링크를 섞을 때, 원래 양이 더 적은 드링크를 절반 버리는 것이 이득이다. 따라서, 드링크의 목록 중 가장 양이 많은 드링크가 기준이 되어, 다른 모든 드링크를 절반씩 섞은 양이 최종 드링크의 최대 양이 된다. [코드] ..

문제 링크 : www.acmicpc.net/problem/20114 20114번: 미아 노트 첫째 줄에 원래 문자열의 길이 N, 세로로 번진 글자의 개수 H, 가로로 번진 글자의 개수 W가 주어진다. (1 ≤ N ≤ 100, 1 ≤ H ≤ 10, 1 ≤ W ≤ 10) 둘째 줄부터 H개의 줄에 걸쳐 N × W 길이의 문자열이 www.acmicpc.net 각 문자열이 번진 형태는 위 그림과 같다. 번진 전체 문자열 중 한 문자당 그 문자가 나타나는 구역이 있음을 캐치하고, 그 구역 내에서 문자를 찾을 수 있다면 그 문자를, 찾을 수 없다면 ?을 출력하도록 한다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..

문제 링크 : www.acmicpc.net/problem/20113 20113번: 긴급 회의 투표 결과 1번 플레이어가 1표, 3번 플레이어가 2표, 4번 플레이어가 1표를 받아 3번 플레이어가 퇴출된다. www.acmicpc.net 단순 구현 문제이다. 동일 득표자가 2명 이상일 시 아무도 퇴출되지 않음에 유의하자. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; typedef pair p; int n, votes[101]; //0: 무..

문제 링크 : www.acmicpc.net/problem/20112 20112번: 사토르 마방진 사토르 마방진에 대해 들어본 적이 있는가? 사토르 마방진은 간단히 말하면 "가로로 읽었을 때와 세로로 읽었을 때 똑같이 읽히는 단어 집합"이다. 예시로는 다음과 같은 것들이 있다. 라팔아 팔 www.acmicpc.net 저번달에 진행됐던 고리콘 문제들을 하나씩 풀이해볼 예정이다. 대회 당일에 토익시험이 겹쳐 대회에 참여하지는 못했지만, 기출문제들을 풀어보고자 카테고리를 개설했다. 맨 처음 문제답게 상당히 간단한 문제이다. 마방진의 크기도 최대 100으로 작기 때문에, 단순한 비교로도 충분히 문제를 해결할 수 있다. 마방진의 i행 j열 문자가 j행 i열 문자와 같은지만 확인해주면 된다. [코드] 1 2 3 4 ..