주간 문제풀이 18 (BOJ 24659 / 18217)

BOJ 24659 - Game with Balls and Boxes

https://www.acmicpc.net/problem/24659

24659번: Game with Balls and Boxes

문제: 번호가 있는 상자와 공이 있고, 목표는 모든 공을 번호가 같은 상자에 도로 집어넣는 것이다. 두 번의 스테이지에 걸쳐 일부 박스를 연 후에 공을 옮길 수 있고, 이 때 박스를 여는 코스트를 최소화하는 것이 목표이다.

 

풀이:

먼저, 문제의 P 순열 기준으로 사이클이 형성되면 그 사이클을 독립적으로 보면 됨을 관찰하자. 그리고, 어떤 사이클에서 특정 부분 배열을 첫 턴에 연다면 그 부분 배열의 첫 번째 박스는 두 번째 턴에도 열어야 함을 관찰하자.

 

각 사이클별로 아래와 같은 dp식을 채운다.

dp[0][i]: i번째 박스를 첫 턴에 열 때, 여기까지 여는 데 드는 최소 비용

dp[1][i]: i번째 박스를 두 번째 턴에 열 때, 여기까지 여는 데 드는 최소 비용

 

두 번째 턴에 열다가 첫 턴에 여는 쪽으로 바꾼다면, 그 바뀌는 시점에 있는 박스는 첫 턴의 비용과 두 번째 턴의 비용을 모두 지불해야 한다. 그 외의 경우는 그냥 첫번째 턴에 열든 두번째 턴에 열든 그 턴의 비용만 내면 된다. 이 점을 이용해서 dp식을 잘 채우면 된다.

 

다만 이 때 사이클의 첫 번째 박스에 대한 dp 배열을 채울 때 그 바로 전에 첫 턴에 열었는지 두 번째 턴에 적었는지 임의로 정해야 하는 문제가 있다. 이건 배열을 두 배로 복사해서 사이클을 한번 더 돌려도 해결이 되고 (내 풀이), 두 경우 그냥 다 해보는 방법이 있다 (다른 분들 풀이: ex. sebinkim님의 47778569번 제출)

 

내 코드: http://boj.kr/781d2f8be48f4386b9a2bc237bfca34a

 

 

BOJ 18217 - Parentheses Editor

https://www.acmicpc.net/problem/18217

18217번: Parentheses Editor

괄호 문자열의 맨 뒤에서 문자를 추가하고 제거할 때, 올바른 괄호쌍의 개수를 온라인으로 구하는 문제.

풀이:

우선은 괄호쌍의 개수를 구하기 위해 필요한 상태를 저장하되, 문자를 삭제할 때 기존의 상태로 롤백이 가능한 persistent한 구조를 만들기만 하면 되기 때문에, 가능한 풀이는 다양할 것 같다.

 

여기서는 일단 내가 처음에 생각했던 (다소 비효율적인) 풀이를 적어둔다.

우선 닫히는 괄호일 때 올바른 괄호쌍의 개수가 증가하는데, 이 때 증가하는 괄호쌍의 개수는 "현재 상태보다 마지막으로 height가 낮았을 때 이후로 현재와 height가 같았던 횟수(height의 정의는 열리는 괄호일때 +1, 닫히는 괄호일때 -1)"인데, 이걸 효율적으로 구하기 위해 각 height마다 vector를 만들어서 그 height에 도달했던 인덱스를 저장해 두고, 각 위치에서 조건에 맞는 횟수를 찾기 위해서 이 벡터 위에서 이분탐색을 한다. 롤백을 하는 것은 단지 이 벡터 위에서 pop을 적절히 하면 된다.

 

코드: https://www.acmicpc.net/source/share/2861f796caf04c1584e1e2c08650e159

다른 풀이를 보았을 때는 굳이 각 height마다의 vector를 써서 인덱스를 명시적으로 저장하지 않고, 열리는 괄호의 위치에 적절히 그 다음 height에 닫히는 괄호가 몇 개 있는지를 저장해두는 방식으로 이분탐색 없이 푸는 것 같다.