njh0602   1년 전

하루종일 고민하고 풀어봤는데 자꾸 시간초과에 걸리네요.. 답은 맞게 나와서(?) 다행인데

최적화를 어디서 해야할지 모르겠습니다.. (아니면 애초에 접근법이 틀렸을 가능성도 있겠네요)

저의 풀이방법은

먼저 입력받은 데이터를 홀수와 짝수로 분리합니다. 그리고 모든 수를 더해봅니다.

Ex) 입력: 2, 3, 4, 6, 7, 8, 11, 15

첫번째수가 짝수이므로 짝수를 왼쪽에 배치함

(2, 4, 6, 8) | (3, 7, 11, 15)

2차원 배열을 만듭니다. (더하기연산)

5 9 13 17

7 11 15 19

9 13 17 21

11 15 19 24

이제 더해서 소수가 되는 경우를 찾을수 있습니다.

소수인지 판별은 에라토스테네스의 체 방법을 썼고 배열을 만들어서 값을 통해 0, 1을 얻어냅니다.

그래서 결국 (1은 소수, 0은 소수 아님)

1 0 1 1

1 1 0 1

0 1 1 0

1 0 1 0

이런 배열을 만들어냅니다.

그리고 각 행에서 하나씩 1을 뽑아낼 수 있으면 답을 구하는 식입니다. 한 번 뽑힌 열은 더 이상 쓸 수 없습니다.

재귀 함수를 이용하여 구현하였고, 뽑힌 열을 저장할 자료 구조는 std::list를 사용하였습니다.

그리고 재귀호출 갯수를 표준화시키기 위해(1 발견시 밑으로 재귀호출) 행을 1의 갯수를 기준으로 정렬했습니다.

Ex)

1 0 1 1 1 0 1 1

1 1 1 0 0 1 1 0

0 1 1 0 1 0 1 0

1 0 1 0 을 1 1 1 0

이렇게 바꿔놓고 재귀 함수를 돌립니다.


이 방법말고 근본적인 해결방법이 있는지 궁금합니다.

appa   1년 전

재귀 함수를 돌면서 지수(exponential) 시간복잡도를 가지므로 시간초과가 발생합니다.

이 문제의 정해는 network flow를 이용한 maximum bipartite matching입니다.

첫번째 숫자와 짝을 지을 숫자(x)를 정한 다음에, 그 둘을 제외한 주어진 수들로 이분그래프를 구성하고 maximum bipartite matching을 구했을 때 모든 것이 매칭이 된다면 x에 대해 가능한 해가 존재하는 것이므로 x를 답에 추가해주면 됩니다.

appa   1년 전

시간복잡도는 O(N * N^3)으로 총 O(N^4)가 되겠습니다. 플로우를 효율적으로 구현한다면 충분히 더 줄일 수도 있습니다.

njh0602   1년 전

결국 재귀함수를 써서 문제가 발생되는 것이었군요...??

appa   1년 전

재귀 함수의 사용보다는 기본적인 접근 방법이 백트랙킹이어서 문제인 것 같습니다.

njh0602   1년 전

아 그렇군요.. 한 번 network flow, maximum bipartite matching 찾아보겠습니다.

감사합니다.

appa   1년 전

http://blog.sisobus.com/2013/10/bipartite-matching...

이 블로그를 보시면 (여러모로) 꽤나 도움이 될 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.