BOJ 중간 점검: 870솔브/1014 컨닝/1017 소수 쌍 간단한 풀이

870솔브 했습니다.

여전히 꿀문제 위주로 푼 것도 사실이긴 한데, 그래도 너무 그러는 것 같아서 1페이지에 있는 비교적 번호 빠른 문제들에 도전해봤습니다.

 

1014 컨닝:

사람을 그래프 정점으로, 컨닝할 수 있는/당할 수 있는 사람의 쌍을 그래프 간선으로 잇게 된다면 그래프에서 최대 얼마만큼의 independent set을 만들 수 있느냐는 문제가 됩니다. 처음에는 그래서 네트워크 플로우를 생각했는데 자기 양 옆 줄의 사람들만 컨닝할 수 있으니까, 결국 홀수번째 줄/짝수번째 줄로 각각 이분 그래프를 만들 수 있게 됩니다. 그래서 이건 Kőnig의 정리에 따라서 이분매칭 문제가 될 수 있고, 실제로 이분 그래프로 잘 만들어 주면 됩니다.

 

1017 소수 쌍:

자연수가 중복되지 않으니까, 1+1=2는 불가능합니다. 따라서 나오는 모든 소수는 홀수이며, 다시 말해서 홀수+짝수 꼴로만 나타내어지게 됩니다.

근데 이게 위랑 좀 비슷한 느낌 안 드나요? 홀수랑 짝수만 더할 수 있으면 결국 홀수 짝수 따로 나눠서 더해서 소수 되는 것만 이으면 이분 그래프로 만들 수 있습니다.

 

첫번째 수랑 어떤 수를 짝짓는 것이 가능한지 모두 확인하는 방법은 다음과 같습니다. 첫번째 수를 홀수라고 가정하면(짝수여도 마찬가지로 해도 됩니다.)모든 짝수 중에서 우선 첫번째 수랑 더해서 소수가 되는 애들을 다 찾습니다. 그리고 그 중 하나를 골라서 첫번째 수랑 그 수를 다 뺍니다.(그래프에서도요!) 그럼 새로운 그래프가 만들어질텐데, 여기서도 완전 매칭이 가능한지를 판단하면 됩니다. 그게 가능한 수들만 모아서 '순서대로' 잘 출력하면 되고, 그게 없다면 '-1'을 출력하면 됩니다.

 

풀었던 문제들 중에서 그럭저럭 난이도 있는(=solved 기준 플래티넘 이상)문제는 이정도였던 것 같네요. 다음은 900솔브로 찾아뵈었으면 좋겠네요.