2022 알고리즘 탐구반 #9

계획

저번에 문제로 넣어놨던 '건포도', '동전0'과 관련이 있는 문제들을 추가했다.
그리고 좀 쉬운 DP 문제도 하나 넣어놨다.

A. 구간 합 구하기 5 (BOJ 11660)

건포도 문제를 풀기 위해 필요한 2차원 누적합 연습

B. 건포도 (BOJ 5463)

무려 5차원 DP. n, m이 최대 50밖에 안돼서 좀 빡세보이지만 O(N^2 * M^2 * (N + M))도 돌아간다. (사실 엄밀히 말하면 N(N+1)/2 * M(M+1)/2 * (N+M)이니까 돌만하다. 그리고 반복문 속에 든게 워낙 간단해서 빠르게 처리된다.)

어떤 직사각형 영역에 대해 가로로 자르거나 세로로 잘라야 한다는 점을 이용해 DP를 생각해보자.

어떤 직사각형을 표현하기 위해서는 가장 왼쪽 위 점과 가장 오른쪽 아래 점의 좌표가 필요하다. (혹은 세로선 2개, 가로선 2개로 생각할수도 있다.) 여기서 대략 N^2 * M^2의 경우의 수가 발생한다.

그럼 이 직사각형을 1*1 크기의 단위 정사각형으로 쪼개기까지 필요한 비용을 d[si][sj][ei][ej]라고 해보자.

만약 직사각형을 세로선으로 자른다고 하면 세로 길이는 원래 직사각형의 길이와 같고 가로길이는 작아지는 두 직사각형으로 나뉘게 된다. 그러면 이렇게 나뉜 두 직사각형을 1*1로 쪼개는 데 필요한 비용에 원래 직사각형에 있던 건포도 수를 더하면 원래 직사각형을 1*1로 쪼개는 데 필요한 금액이 된다.

식으로 표현하면 d[si][sj][ei][ej] = d[si][sj][i][ej] + e[i+1][sj][ei][ej] + s[si][sj][ei][ej]라고 할 수 있다. (s[si][sj][ei][ej] = 직사각형 si sj ei ej에 있는 건포도의 수)

여기서 최솟값을 구해주기 위해 i를 si부터 ei-1까지 돌려주면 된다.

마찬가지 방법으로 가로선에 대해서도 해결해주면 된다.

이때 조심해야할 점은 DP테이블을 채울 때 순서를 신경써야 한다는 것이다.

문제의 특성상 작은 직사각형부터 채워주면 된다.

IOI에 출제된 문제이지만 IOI 문제중에서 쉬운 문제로 꼽히는 문제이다. IOI라고 너무 겁먹지는 말자.

처음반 겨울학교였나? 실습문제로 나오던 문제였다.

C. 동전 1 (BOJ 2293)

전형적인 DP 문제

k까지만 DP테이블을 관리해주면 된다.

D. 동전 0 (BOJ 11047)

얘는 그리디다.

동전의 가치가 배수관계로 주어지기 때문에 항상 더 높은 가치의 동전을 많이 사용하는 게 이득이기 때문이다.

E. 자동차경주대회 (BOJ 2651)

N^2 DP로 풀면 된다.

동전 1보다 쉽다고 생각한다. 혼자 풀어보게 하자.

이화여대 대회 신청 얘기하기 http://cse.ewha.ac.kr
1학년 후배는 국제정보올림피아드 교육생 서류 붙어서 면접 대비로 발표시키기

---

결과