일본정보올림피아드 예선 - 2010

문제 세트를 올릴 때에는 그 세트의 모든 문제를 푼 후에 올리겠다고 생각했었는데, 그 동안 제대로 모두 푼 문제 세트가 없어서(...) 올리지 못했다. (최근에 하나 더 추가 되기는 했다 ^^;)

6/25일 아침에 시간잡고 푼 문제 셋 - 일본정보올림피아드 2010 예선

링크는 BOJ 기준이다.

1. 영수증

10권 중 나머지 9권의 가격의 합을 10권 전체 가격의 합에서 빼면 나머지 한 권의 가격이 나온다.

2. 주사위 게임

말판의 지시를 기록해놓고, 주사위 던지는대로 시뮬레이션하면 된다.

3. 결혼식

주어지는 친구 간선으로 그래프를 그린다. 이후 상근이를 기준으로 거리가 2인 친구들은 모두 초대할 수 있다. 이를 BFS를 통해 확인할 수 있다. O(M)

4. 카드놓기

카드를 모두 선택하는 경우의 수를 생각하면 n^k 만큼 생김을 알 수 있다. 이 때, 카드의 수 n이 10 이하이며 선택하는 카드의 수 k가 4 이하이므로 10^4 의 카드조합만큼만 생겨 모든 카드를 만들어보는 것으로 카드의 조합을 구할 수 있다.

문제가 되는 부분은 이어붙인 카드로 만든 수가 겹치는 경우인데, 만든 카드의 최대값은 1억 - 1만큼 되기 때문에 배열에 저장하는 것으로 판단할 수 없다.

이를 해결하기 위해 배열을 선언하여 판별하지 말고, map을 이용하여 실제로 만들어지는 값 만큼의 메모리만 사용하도록 하면 해결할 수 있다.

O(kN^klgN)

5. 출근 경로

DP[direct][i][j] = (direct를 방향으로 하며 북으로 i, 동으로 j번째 교차로에 도착하는 경우의 수)

간편하게 방향을

0 : 북

1 : 동

으로 설정하면

DP[0][i][j] = sum(DP[1][k][j])  (∵ k = 1 to i - 2 )

DP[1][i][j] = sum(DP[0][i][k])  (∵ k = 1 to j - 2 )

를 만족한다.

이를 계산하기 위해 DP[direct][i][j]의 누적합을 저장하는 S를 만들어서 계산하면 O(WH)에 해결할 수 있다.

6. 산타클로스와 루돌프

처음 두 번을 문제의 조건을 잘못 읽고 풀었다. (방문한 집 위로 이동할 수 있다던지...현재 집과 방문하려는 집 사이에 방문하지 않은 집이 있어도 갈 수 없다라던지..)

작성자가 푼 방법은 다음과 같다.

문제 조건에서 건물들이 최대 24개까지 존재할 수 있기 때문에, 처음에 Bit DP로 접근하려 했지만, 실제 배열을 선언하면 24 * 2^24 = 402653184 > 4억 개 만큼의 공간이 필요하기 때문에 메모리 초과가 난다. 이 때문에 이차원 배열을 선언하는 형태로 Bit DP를 하긴 어렵다.

이후 생각한 방법은 전체의 경우를 다 탐색해보는 Back Tracking 방법이다. 정점의 수가 적고, 제약으로 인해 실제로 도달할 수 있는 경로는 적을 것이라는 판단.

산타는 교회 또는 집으로만 이동해야 하기 때문에 교회와 집들에 번호를 매겨 정점으로 만든 후, 각 정점끼리 이동할 수 있는지에 대한 여부를 인접행렬로 표현하였다. 이후, 교회에서부터 이동 가능한 정점들을 순회하고, 갈 수 없을 경우 퇴각하는 방법을 고안할 수 있다.

현 방법을 단순하게 돌리면 무조건 TLE가 날 것이다. 이를 해결하기 위해서 어떤 조건을 걸고, 어떻게 들어가는 시간을 압축(?)할 수 있을지 생각해보아야 한다.

일단 판단하는 과정에서 들어가는 시간을 줄여야 한다.

1. 탐색 과정에서 이동하려는 정점의 방문여부를 현재 존재하는 정점의 수(앞으로 V라고 하겠다)만큼 탐색해보지 않고, Bit를 이용하여 상태를 표시하는 것으로 V만큼의 시간을 절약할 수 있다.

2. 탐색 도중, 현재 위치와 방문하려는 정점 사이에 이미 방문한 정점이 있는지 판단해야 한다. 이를 위해 인접행렬을 만드는 과정에서 정점과 정점 사이에 존재하는 정점들을 Bit 형태로 저장한 배열을 만들어 놓는다. 이후, 탐색 과정에서 이미 방문한 정점들과 현 정점과 방문하려는 정점 사이에 존재하는 정점들의 값에 대한 AND 연산을 통해 현 정점과 방문하려는 정점 사이에 존재하는 이미 방문한 정점들을 알 수 있다. 이를 통해 시간을 단축시킬 수 있다.

위 과정들을 통해 탐색에 들어가는 시간을 압축하면 대략 10~20초 사이에서 가장 큰 사이즈의 마을이 해결될 것이다. 이 시간을 더 줄이기 위해서는 탐색하는 과정을 줄일 필요가 있다.

탐색 과정을 줄이는데에 가장 중요한 것은 불필요한 과정을 없애는 것이다.

이를 위해 현 상태에서 이후에 어떠한 경우에도 조건을 만족하며 교회로 돌아갈 수 없는 상태들을 걸러내는 방법을 생각해내야 한다.

탐색 과정을 줄이기 위해, 현재 내가 있는 정점의 위치와 이미 방문한 정점들 이후로 도착하는 것이 가능한지를 저장하는 배열을 만든다.

하지만, 이 과정에서 Int형은 당연히 선언할 수 없고, Bool을 사용해도 MLE가 나온다.(Bool형은 참, 거짓밖에 판별 못하지만 1byte를 잡아먹는...)

그럼, 이를 어떻게 해결할 수 있을까?

본인은 해결할 방법이 생각나지 않아, 직접 1bit 짜리 자료구조를 만들기로 했다.

unsigned int형은 최대 2^32 까지를 표현할 수 있고, 실제로 사용되는 메모리도 32bit이다. 즉, 우리는 unsigned int형을 사용하여 1bit씩 나누어 사용할 수 있다.

실제로 이를 구현하면 50000KB라는 빡빡한 메모리 사용을 보이면서 해결할 수 있다. ^^;;