ksc919   4년 전

질문드려도 되나요?

코딩 처음시작하면서 백준풀고 있는 사람인데,

백준에서 풀었던 문제랑 비슷한 코포문제를 찾아서 풀고 있거든요/

근데 코포문제는 질문할 곳이 없어서요 ㅠㅠ

이 게시판에 코포질문 올려도 괜찮나요?

djm03178   4년 전

네 괜찮습니다.

ksc919   4년 전

ㅠㅠㅠ 감사합니다. 새로 글 쓸게요.

ksc919   4년 전

https://codeforces.com/contest...

지금 겨우 코딩시작한 입장이라, 배울 게 쌓여 있지만 ,계속 PS를 해나가는 과정에 꼭 필요할 거라 생각해서 질문드립니다.

위 문제를 보고 백준의 설탕배달문제(https://www.acmicpc.net/proble...)를 떠올렸습니다.

같은 로직으로 코드를 구현했고, 테스트는 통과했습니다.

그런데 테스트케이스가 10000개가 되니 TLE 가 떴습니다.

1부터 N까지 하나하나 카운팅해나가다보니 ⌈n/3⌉이란걸 '관찰'을 통해 알았습니다.

질문>

입력되는 모든 경우에 대해 ⌈n/3⌉성립함을 어떻게 증명해야 할까요?

단순히 '이걸로 풀면 될거같다!' 라는 생각으로 문제를 풀었습니다. 이번에는 운좋게 맞았는데... 백준 게시판을 봐도 그렇고, 테케를 통과하는데

반례가 생기는 경우가 많은 것 같더라고요. 결국 처음 구현할 때 사고의 헛점,구멍이 많아서 생기는 문제가 아닌가 싶어서, 지금부터 증명을 계속 해나갈 계획을 세웠는데, 잘 모르겠네요. 어떻게 증명을 해야할지...

그리고, 종만북 정당성증명 파트를 보면 귀납법 등 몇가지 테크닉이 나오는데, 그 정도의 테크닉만 알면 알고리즘 공부하는데 문제가 없을까요??

수능에서 수학문제만 풀다가, 무언가를 '증명'하려고 하니까 방법도 모르겠고, 내가 하는 증명이 옳은지도 모르겠고... 숨이 턱턱 막힙니다ㅠㅠ

조언 부탁드립니다...

djm03178   4년 전

코포 2A에 저런 게 나오면 증명하라고 내는 문제는 아닙니다. 그냥 '감'으로 규칙을 찾을 수 있으면 됩니다. 2A에는 떠올리기는 쉽지만 증명하기가 까다로운 문제가 아주 많습니다. 출제자들도 그걸 알고 자주 이런 문제를 내는데, 그러다 보니 간혹 이게 떠올리기도 어려우면 셋 밸런스가 산으로 가기도 합니다.

djm03178   4년 전

이 문제의 경우는 일단 3만 써서 아무리 빠르게 가려고 해도 n/3보다 빠를 수 없고, 그 외에는 n%3의 값에 따라 3으로만 가는 경우, 2를 하나 쓰는 경우, 2를 둘 쓰는 경우로 나누어 모두 ceil(n/3)이 됨을 보이면 될 것 같습니다.

ksc919   4년 전

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

제 생각으로는, 이 정도 증명도 힘든데, 난이도가 더 높은 문제들에 필요한 증명을 할 수 있을까 입니다 ㅠㅠ

목표가 코포 오렌지라... 많이 높습니다. 

조바심 없애야 하는 걸 아는데 쉽지가 않네요 ㅎㅎ

하나만 더 질문드려도 될까요??

학교에서 수학수업을 들으려고 하는데, 제 목표인 코포 오렌지를 고려했을 때 정수론수업을 들을지 이산수학 수업을 들을지 고민입니다.

그리고 ps에 필요한 사고력은 문제풀이훈련 말고는 다른 방법은 없는걸까요??

djm03178   4년 전

전 수학을 너무 못하고 코포에서도 수학 문제만 나오면 풀질 못합니다. 제 생각에는 이산수학은 들어두면 좀 다양한 문제의 해결에 도움이 되고, 정수론은 좀 더 정수론 전문적인 문제들에서 유용한 것 같습니다. 정수론은 남이 못 푸는 문제를 하나 더 공략하고 싶을 때 유용한 것 같습니다.

ksc919   4년 전

감사합니다! 분발할게요 ㅎㅎ

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