kk3085   2년 전

제가 테스트 했을 때는 정답이 나왔지만 런타임에러가 나옵니다.


여기서 bool paper 배열이 용량 최대치를 넘겨 런타임에러를 발생시키는 것 같은데


런타임에러를 발생시키지 않을 만큼 메모리를 적게 사용하는 문제해결방법에 대한 힌트를 주셨으면 합니다

jh05013   2년 전

메모리를 줄이더라도 종이를 직접 구현하는 방법으로는 시간/메모리 초과를 피할 수 없습니다.

힌트는 포함배제의 원리입니다.

chogahui05   2년 전

전형적인 포함 배제 문제이긴 한데

아마도.. 교집합 연산을 구현하기가 어려우셨으리라 생각이 되는군요.

a의 배수이면서 b의 배수이려면 a와 b의 최소 공배수의 배수여야 겠죠..


그나마 다행인 것은

소인수 분해가 안 나왔다는 것인데요.. 보통 정수쪽에서 포함 배제 냄새가 나는 경우에는..

(제가 백준에서 문제를 푼 경험으로는) 소인수 분해를 착실하게 해야 하는 경우가 많더라고요.

그런 경우에는 문제가 어려워지는데요.

대표적인 예로는 최소 인수라던지. 제곱 ㄴㄴ가 있겠네요. 물론, 이번에 올라온 세 쌍 서로수도 그런 류고요.


포함 배제 자체는 어려운 이론은 아니지만

활용해야 하는 경우가 나오면 극단적으로 어려워지는 경우가 있어요. 조심하셔야 해요..


그런 문제들은 원하신다면

추천해 드리겠습니다. 아주 쉬운 것부터 난이도별로 차근차근 푸실 수 있게..

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