TopCoder SRM 566 Div2

2012. 01. 13.

[ kcy1019 ]

2

646.57

0

0.00

1

-25.00

0.00

621.57

1189

1327

운이 좋아서 드디어 블루로 등극 ㅜ_ㅜ 내가 1군이라니!

가서 잘 할 수 있을지 모르겠지만.. 일단 기쁘다 ㅋㅋ

250 - 언제나 그렇듯이, Div2 250은 쉽다.

문제설명 : 8퍼즐과 비슷한 펭귄 퍼즐을 맞추는데,

여기선 가로나 세로로 연속된 것들을 한 번에 옮길 수 있고,

숫자가 없이 모두 같은 무늬가 그려져있다.

퍼즐의 상태가 주어졌을 때, 최소 몇 번의 행동으로 퍼즐을 맞출 수 있을까?

조건을 보면 답은 자연히 0, 1, 2 세 가지 경우밖에 생기지 않는다는 것을 알 수 있다.

0 : 제대로 맞춰져있는 경우

1 : 한 번만 옮기면 되는 경우, 그러니까, 

PP.

PPP

PPP

처럼 되어있는 경우이다.

이런 경우 . (빈 칸)을 포함한 줄을 세로로 한번만 밀면 된다.

2 : 두 번 옮겨야 하는 경우. 예를 들면

P.P

PPP

PPP

처럼 되어있는 경우이다.

이 경우에는 세로로 한 번, 가로로 한 번 옮겨야 한다.

500 - 전형적인 dp문제가 나왔다!

문제설명 : 펭귄 매칭 회사 (결혼정보업체..?) 에서 펭귄들을 매칭시켜주는데,

각 펭귄에게 빨간 색과 파란 색중 어느 색을 좋아하는지 물어본 뒤,

같은 색을 좋아하는 펭귄들끼리 이어준다.

그런데, 여기서 펭귄들은 모두 원 위에 같은 간격만큼 떨어져서 배치되어있고,

두 펭귄을 이을 때 선을 긋는데, 이 선끼리 겹치는 경우가 생겨서는 안 된다.

이러한 조건을 만족시키면서 만들 수 있는 펭귄 쌍의 최댓값은 얼마나 될까?

이게 사실... 엄청나게 유명한 문제인걸로 안다

(그래서인지 div2에 나왔음에도 많이 풀린 것 같다).

일단 난 DP를 이용하여 풀었는데,

선끼리 겹치지 않아야 한다는 점에 착안해서 생각해보자.

원 위의 임의의 두 점을 이었다면,

그 점을 기준으로 이 문제는 두 개의 부분 문제로 나눠질 수 있다:

그 두 점보다 위쪽에 있는 점들끼리 이어보는 문제와

그 두 점보다 아래쪽에 있는 점들끼리 이어보는 문제.

이런 식으로 생각해보면,

dp[i][j] = i번째 점 부터 j번째 점 까지 이었을 때, 펭귄 쌍의 최댓값

이라고 정의할 수 있고,

j번째 점과 i <= k < j인 k번째 점을 연결시켰다고 보면,

dp[i][j] = max { dp[i][k-1] + dp[k+1][j-1] + canConnected[k][j] | i <= k < j }

과 같은 점화식을 세울 수 있다.

여기서 canConnected[i][j] 는 i번째 점과 j번째 점이 이어질 수 있는가, 즉,

"i번 펭귄과 j번 펭귄이 좋아하는 색이 같은가?" 이다

(문제의 조건에 따라, 이 때에만 이을 수 이기 때문에).

 1000 - 기하문제.. 에디토리얼이 나오면 봐야지 도저히 생각이 안 난다..

기둥의 좌표와 펭귄들의 좌표가 주어졌을 때, 주어진 펭귄들을 모두 감싸면서

주어진 기둥들의 일부를 꼭짓점으로 하는 다각형의 넓이의 최솟값을 구하여라.