0825 Problem Solving
2020년 2차 선발고사를 쳐봤습니다. 아이싱 문제는 풀이를 이전에 접한 적이 있어서, 첫 3문제만을 풀었습니다. 결과 : 150 / 43 / 18 1. 마법의 다이얼 먼저 좌표 압축을 한 뒤, 각 다이얼 기준으로 i번째 칸에 다이얼을 모으게 될 때 얼마나 돌려야 할지를 생각해보자. 이는 함수 y = ax + b 꼴들로 나타내어지며, 따라서 각 칸 별로 x의 계수, 상수항을 저장해둔 뒤 prefix sum을 잘 관리해주면 풀 수 있다. 2. 하나 둘 셋 43점 (서브테스크 1, 2) : 먼저 다항식 시간복잡도의 풀이를 위해선 다음과 같은 아이디어를 얻어야 한다. (1, 2, 3) 쌍의 개수와 (3, 2, 1) 쌍의 개수를 정하고 생각해보면, 1과 3의 위치를 그리디하게 선택 가능하고, 무슨 1을 무슨 3..