2021 NYPC 연습문제 풀기

2021년도 NYPC가 내일 시작한다. 연습문제 2개가 올라와서 풀어보았다.

1. 최대구간합

너무 유명한 문제다. $dp[i] = max(dp[i-1]+a[i],\,\, a[i])$

 

2. 도토리를 주워라

출력 결과만 제시하면 되지만, 그냥 평범한 문제라고 생각하고 풀어 보자.좌우로 움직이는 것이 자유롭기 때문에 칸별로 보는것보다는 움직일 수 있는 구간별로 보는 것이 좋다.

 

만약 어떤 두 구간 사이에 유저가 존재한다면 두 구간에 있는 도토리를 동시에 먹을 방법이 없다.따라서 dp를 다음과 같이 세운다:

 

$dp[i][j]=$ $i$번째 가로줄에서 $j$번째 구간에 있는 도토리를 모두 먹을 때 최대 도토리의 개수

 

구간끼리의 연결 관계를 설정하면 상태 전이는 $dp[i][j] = max(dp[i-1][k])$ (단, $k$는 $(i, j)$와 연결된 $i-1$번째 줄의 구간 번호)가 된다. 약간 DAG에서 위상정렬 해놓고 dp치는 느낌이다.

 

이렇게 해놓으면 추적도 엄청 쉽다. $tr[i][j]$라는 배열을 만들고 위쪽에서 마지막으로 $dp[i][j]$를 갱신시킨 k값을 저장해놓는다.

$(i, j)$에서 $(i-1, k)$로 추적하자.

 

그 뒤에 각 구간에서 LR 도배로 모든 도토리를 먹고, 연결된 점을 찾아서 거기까지 L 도배로 이동한다. D 한번 치고 반복.

그러면 순식간에 맞을 수 있다~~

 

처음에는 경로를 출력하는 게 귀찮아서 그냥 구간만 알아놓고 내가 직접 시뮬레이팅해서 답을 내려고 했는데, 더럽게 헷갈려서 포기했다. 나처럼 게으른 사람들은 차라리 코딩하는 게 낫다.

 

대충 골1 느낌인데 플5도 잘하면 받을 수 있는 문제같다. 시간을 들여 푼 게 오랜만이라 재밌었다.