안녕하세요 hellogaon입니다.
한양대학교 에리카 프로그래밍 대회, 2018 HEPC - MAVEN의 출제 및 검수를 진행하였습니다!
끝난 지 한참 지난 대회지만 추후 많은 분들이 대회를 준비하실 때 많은 분들에게 도움이 되고자 풀이 및 코드를 작성하였습니다.
A - 15725번: 다항함수의 미분
첫째 줄에 최대 일차 일변수 다항식이 주어질 때 주어진 다항식을 미분한 결과를 출력하는 문제이다.
최대 일차 일변수 다항식이기에 상수항만 있을 수도 있으므로
x가 있을 경우 계수가 있다면 그 계수를, 없다면 부호에 따라 1 또는 -1을 출력하며
x가 없을 경우 0을 출력하면 되는 문제이다.
B - 15726번: 이칙연산
세 수가 주어질 때 사이에 곱셈 기호, 나눗셈 기호를 한 번씩 사용하여 만든 식 중 가장 큰 값을 출력하는 문제이다.
C언어에서 두 정수를 나눗셈 할 시 올바른 값이 나오려면 double로 형변환을 하여야 한다.
또한 답이 int범위를 넘지 않더라도 1,000,000 * 1,000,000을 수행할 시 int가 담을 수 있는 범위를 넘게 되므로
long long과 double을 상황에 맞게 사용해주면 되는 문제이다.
C - 15727번: 조별과제를 하려는데 조장이 사라졌다
성우는 1분에 1에서 5까지의 거리를 이동할 수 있을 때 주어진 거리를 최소 몇 분만에 갈 수 있는 지 출력하는 문제이다.
주어진 거리를 5로 나눈 값을 올림한 값을 출력하면 되는 문제이다.
D - 15728번: 에리 - 카드
N장의 '공유 숫자카드'와 N장의 '팀 숫자카드'에서 상대팀은 최선의 방법으로 K장의 '팀 숫자카드'를 견제 할 때
우리 팀이 얻을 수 있는 최대 점수를 출력하는 문제이다.
이 문제를 탐욕법으로 접근하기에는 음수 * 음수가 가장 큰 점수를 낼 수 있기 때문에 조심하여야 한다.
N이 100으로 작기에 매번 모든 경우를 완전탐색 기법을 사용하여 조사해볼 수 있다.
모든 경우를 다 해봤을 때 가장 큰 점수가 나오는 '팀 숫자카드'를 K번 반복적으로 견제하는 작업을 수행한 뒤
다음 나오는 가장 큰 점수가 답이 된다.
k번째 견제 시, N-k개의 '팀 숫자카드'만 확인하며 제거할 카드를 맨 뒤에 있는 N-k번째 카드와 바꾸어 주면
좀 더 쉽게 구현할 수 있다.
E - 15729번: 방탈출
현재 모두 불이 꺼진 상태에서 문제의 주어진 규칙을 따라 입력으로 주어지는 상황을 만들 때
최소 몇 개의 버튼을 눌러야하는 지 출력하는 문제이다.
규칙을 몇 번 수행하다보면 아래가 성립하는 것을 알 수 있다.
1. 버튼을 누르는 순서는 관계가 없다.
2. 불이 모두 꺼진 상태에서 원하는 상태를 만드는 것과 원하는 상태에서 불이 모두 꺼진 상태를 만드는 것은
눌리는 버튼이 동일하다.
탐욕법을 이용하여 원하는 상태에서 불이 모두 꺼진 상태를 만들 때 앞에서부터 보면서 불이 켜져있다면
그 버튼을 누르는 것이 최선이고 오른쪽 두 개의 버튼도 반전시켜주는 작업을 반복한다면 답을 구할 수 있다
F - 15730번: 수영장 사장님
산의 지형이 주어질 때 물이 얼마만큼 고일 수 있는 지 출력하는 문제이다.
priority_queue를 이용한 풀이도 있지만 내가 푼 방법은 다음과 같다.
먼저 높이마다의 현재 지형을 구한다. 높이 h의 단면을 구하고 싶다면 모든 N,M에 대하여
문제에 주어진 mat[n][m]이 h보다 크다면 지형이 없는 곳이므로 0, 아니라면 1로 단면을 구성한다.
이후 BFS를 이용하여 고여있는 부분만을 구해서 더해주게 되면은 시간복잡도가 O(NMH)만에 풀 수 있는 문제이다.
고여있는 부분을 구하는 방법은 0인 테두리를 한칸씩 만든 뒤 그 테두리에서 BFS를 돌려 인접한 0인 칸을 1로 만들어준다.
이제 이 층에서 1이 아닌 부분은 물이 고일 수 있는 부분이 되므로 이들을 세어주면 문제를 풀 수 있다.
G - 15731번: Python 문법
파이썬의 두가지 구문이 주어질 때 이 구문으로 만들 수 있는 python indentation을 만족 시키는
서로 다른 경우의 수를 출력하는 문제이다.
이 문제는 DP를 이용하여 dp[x][y]를 x번째 글자가 y칸 들여쓰기를 했을 때의 경우의 수라고 정의하게 되면,
초기값으로 dp[0][0] = 1을 주고,
ch[x-1] == ' f '라면 한 번 들여써야 하므로 모든 y에 대해 dp[x][y] = dp[x-1][y-1],
ch[x-1] == ' e '라면 들여쓰기를 안할 수도 있고, 들여쓰기를 할 수 있는 만큼 할 수 있으므로,
dp[x][y] = dp[x][y+1] + dp[x-1][y]이 되게 된다.
dp배열을 완성 한 뒤, 모든 y에 대해 dp[N-1][y]를 더해주면 풀 수 있는 문제이다.
경우의 수가 많을 수 있으므로 나눈 나머지를 구하는 부분은 정수론을 사용했다.
H - 15732번: 도토리 숨기기
D개의 도토리를 규칙에 맞게 앞에서부터 차례대로 넣을 때 마지막 도토리가 들어가는 상자번호를 출력하는 문제이다.
몇 번째 상자가 마지막 도토리가 들어가는 상자인가?를 몇 번째 상자까지 D개를 담을 수 있는가?라고 변형한다면
수치해석에서의 이분법을 사용하여 풀 수 있다.
각각의 규칙이 A부터 B까지 C간격으로 있을 경우,
mid번째 상자 전까지 A, B사이에 있을 때 (min(B,mid)-A)/C+1개의 도토리를 담을 수 있다는 것을 계산할 수 있다.
모든 규칙으로 나온 값들을 더한다면 mid번째 상자까지 D개를 담을 수 있는 지 없는 지를 O(K)만에 판단할 수 있게 되며
이에 이분법을 적용한다면 O(KlgN)만에 문제를 해결할 수 있다.
