주간연습 (3) - 2023.09.04 ~ 2023.09.11

마지막 수정 시각: 2023-09-14 21:08:23

12개 중에 7개를 풀었다. 한 7개 정도 적당히 푸는게 부담은 덜한 것 같다.

A. BOJ 25345 (AC)

처음에 지문을 잘못 이해해서 많이 헤맸다. 높이 배열을 마음대로 지정할 수 있다는 점을 이용해서 조합 문제로 환원할 수 있다.

B. BOJ 22965 (AC)

이미 정렬되어있으면 한번, rotate해서 만들 수 있으면 두번, 그렇지 않으면 세번으로 충분하다.

C. BOJ 17497 (AC)

이진수로 변환해서 생각하면 답을 비교적 쉽게 유도할 수 있다.

D. BOJ 17623 (AC)

DP로 모든 경우를 확인해주면 풀린다.

E. BOJ 1587 (PASS)

처음에 그냥 이분매칭 구하라는 건줄 알았는데 잘 보니 아니었다. 좀 고민해보면 케이스 분류로 그리디하게 해결이 될 것 같은데 생각하기 귀찮고 풀기 싫어져서 그냥 패스했다.

F. BOJ 16763 (AC)

\(y_i\) 값을 고려해서 \(k\)지점을 거쳐서 가는 경우의 최단거리를 다익스트라 한 번으로 구할 수 있다. 이 값과 그냥 다익스트라로 구한 값이랑 비교하는 식으로 문제를 풀 수 있다.

G. BOJ 25406 (AC)

올바른 식사 계획에 따라 방문하는 그리디 전략은 어렵지 않게 유도할 수 있다. 전략 유도보다는 구현이 까다로운데 자료구조를 잘 써서 열심히 구현하면 된다.

H. BOJ 1055 (AC)

유명한 유형의 문제. $가 1개일 때는 쉽고, 두 개 이상일 때는 반복할 때마다 길이가 두배씩 길어지는 셈이므로 최대 확인해야하는 재귀횟수가 많지 않다는 걸 알 수 있다. 각 단계의 길이가 얼마인지를 미리 계산해서 저장해두면 로그 시간에 특정 위치의 문자가 무엇인지 계산할 수 있다.

I. BOJ 3789 (PASS)

Suffix Array를 잘 응용하면 풀릴 것 같은데 여기까지 고민하고 말았다. 더 풀 시간(이라기보단 의지)이 없었다.

J. BOJ 18839 (PASS)

문제도 안 읽어봤다.

K. BOJ 29202 (PASS)

문제도 안 읽어봤다.

L. BOJ 11622 (PASS)

문제도 안 읽어봤다.