rdd6584   3년 전

조세퍼스 문제2까지는 세그먼트 트리를 이용해서 풀었는데 조세퍼스 문제3은 dp를 이용한다는 것을 알아도 어떻게 풀수 있을지 감이 안오네요.

평소에는 모르는 문제가 나와도 해법을 보지 않고, 나중에 기회되면 다시 풀어보는 방법으로 했는데 보통 어떻게 하시는 편인가요?

chogahui05   3년 전

전 미뤘다가 나중에 푸는 편입니다.

정 안된다면 반례를 찾아보는 것도 생각하고요. 그런데 사실 짧은 시간에 cp를 준비하기에는.. 흐음..

제가 여기서 문제 푼 지 11개월이 되었는데요.. kmp라던지 mcmf라던지 유량 같은 것은

아직 못했어요. 보통 1년 정도 하면 맛이라도 봐야 하거든요..


물론, 완전하게 해법이 보이지 않는 경우에는 알고리즘을 배워보고 나서

풀어보시는 것도 나쁘진 않아요. 잘 짜시는 분들 블로그에 들어가서 베껴도 보시고.. 

(그렇다고 10초만에 베낀 거 제출하고 그러라는 건 아닙니다.)

자기걸로도 만들어 보시고.. 그래서 책이라는 게 있잖아요.. 종만북이라던지..


그런데 전, 일단 배운 데 까지라도 적용을 할 수 있으면 충분히 적용을 하는 편입니다.


예를 들어서. 저 같은 경우, 이분 매칭만 아주 약간(?) 해 본 상태에요.

https://www.acmicpc.net/proble...

이런 문제가 있어요. 그러면 여기까진 생각해 볼 수 있겠죠.


어? 일단 나누는 거네?

그런데, 같은 팀끼리 연결된 걸 나눌 때랑, 다른 팀이 연결된 걸 나눌 때 컷 비용이 같진 않겠구나. 그러면 어떻게 풀어야 하지?

여기까지만이라도 나가보자는 거죠. 아는 데까지만이라도..

chogahui05   3년 전

그런데, 솔직히 rdd님.. 되게 금방 하실 거 같아요. 그러니까 너무 걱정은 하지 마세요~

그 문제 푸신 거 보고..

subinium   3년 전

조세퍼스 문제 3 같은 경우는 O(n) 의 풀이로 반복문으로 풀면됩니다.

저 같은 경우엔 해법보단 다른 분들의 질문을 먼저 보는 편입니다. 문제에서 막히는 부분은 비슷한 점이 많더라구요
아닌 경우엔 그 문제와 관련된 다른 문제를 차근차근 풀어보는 편입니다. 저는 한동안은 순열 문제를 풀기위해 세그먼트와 펜윅 트리
문제들부터 차근차근 풀었네요.
그래서 조세퍼스 문제 3 같은 경우에는 O(n)풀이를 생각하기 위해 다른 조세퍼스 문제를 찾아보면 좋을 거같네요
이 문제 전에 https://www.acmicpc.net/proble... 를 풀어보시면 더 감이 올거 같네요

rdd6584   3년 전

우선 chogahui05님 그때 블로그에서 도와주셨던 그 분이시군요.

답변 진심으로 감사드립니다.


덕분에 어떤식으로 공부해야 할 지 감이 오네요. 우선 아는거라도 최대한 활용해서 어느정도 단추를 꿰놓고 부족한 부분은 따로 공부해야겠네요. 저도 공부하다보면 아 그때 못풀었던 그 문제는 이 알고리즘으로 풀면 되겠구나. 같은 감이 올때가 종종 있더라구요. 종만북도 지금 가지고는 있는데, 내용이 이해하기가 힘들어서 보는게 꺼려지고 막 그러네요. 좀 진득하게 공부할줄도 알아야하는데ㅠㅠ

답변 감사합니다!

rdd6584   3년 전

subinium 님 답변 진심으로 감사드립니다.
관련된 문제부터 차근차근 풀어보는거 되게 좋은 공부방법인거 같아요.
추천해주신 문제 꼭 바로 풀어볼게요!

조세퍼스 문제들은 그때는 세그먼트 트리를 몰라서 2번문제만 해도 무척 어렵게 느껴졌었는데, 3번은 더더욱 어렵네요.

중간 순서를 직접 구하지 않고도 마지막 순서를 알 수 있는 해법이 있을거 같은데, 생각이 안나네요. 다른 문제들 풀면서 천천히 생각해볼게요.
답변 감사합니다.

rdd6584   3년 전

두분들 덕에 문제 해결할 수 있었습니다. 감사합니다.

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