ksc919   4년 전

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

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

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

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

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

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

질문>

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

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

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

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

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

조언 부탁드립니다...

prarie   4년 전

일단 코드포스는 각 콘테스트마다 editorial (solution) 이 있습니다.

그걸 참고하거나, 만약 부족한 부분이 있다면 comments들을 보면 사람들의 풀이가 다양하게 쓰여 있습니다.

이 문제의 경우 +- 2, 3 칸씩 움직일 수 있는데, 경우를 나눠 다음과 같이 생각할 수 있습니다.

i) N % 3 == 0

이 경우 3을 N / 3 번 쓰는게 무조건 최적입니다.

ii) N % 3 == 1

이 경우, 2->2->3->...->3 으로 가는게 최적입니다.

-> 2 대신 3을 무조건 많이 쓰는게 좋기 때문에, 2를 최대한 적게 쓰고 완성할 수 있는 방법은 2를 2번 쓰는 것입니다. 2를 2번 쓰면 (N - 4) 는 무조건 3으로 나누어 떨어집니다.

따라서 (N - 4) / 3 + 2 가 됩니다. = (N - 1) / 3 + 1 = (N + 2) / 3

N % 3 == 1 이므로, (N + 2) / 3 은 ceil(N / 3)

단, 이 경우에는 N >= 4 일 때만 성립합니다.

(즉, N = 1 일 때는 예외처리 해야 합니다)

iii) N % 3 == 2

이 경우, 2를 한번 쓰고, 3을 다 쓰는게 최적입니다.

따라서 1 + (N - 2) / 3 = (N + 1) / 3

N % 3 == 2 므로, (N + 1) / 3 == ceil(N / 3)

N > 1 인 경우 따라서 ceil(N / 3) 이 성립합니다.

저 같은 경우에는 대회 중에 3가지 케이스를 나눠서 if문으로 짰었습니다.

코포 유형을 공부한다면, 그냥 코포 A~C번을 최대한 많이 풀고, editorial을 확인하는 방법이 가장 좋을 것 같습니다.

ksc919   4년 전

답변 정말 감사드립니다.

저런식의 증명공부는 어떻게 훈련해야 할까요??

전 숫자 쭉~ 나열해서 규칙보이면

대충 규칙대로 이거면 되지 않을까? 라고 코드에 들어가거든요...

제가 생각해도 엄밀함이 너무 떨어집니다...

써주신 댓글을 보면서도 문제푸는 와중에 저렇게 어떻게 할 수 있을까 란 고민이 먼저 듭니다...

prarie   4년 전

최대한 많은 문제를 접하는 게 맞다는 결론이 나오네요

문제를 푼 뒤에 (또는 못 풀겠다 싶으면) 해설을 보고 접근 방식을 익힌 뒤 나중에 또 비슷한 문제를 보면 최대한 적용하려고 노력하는 것 외에는 딱히 방법이 없다고 생각해요.

저 같은 경우에는 비슷한 유형의 문제에 3~4번 처맞다 보니까 어느 순간부터 잘 풀게 되더라고요. 천재라면 바로 풀거나 공부한 뒤 바로 적용할 수 있겠지만, 일반인이라면 당연한 절차 같아요.

문제를 정말 많이 풀다 보면 어느 순간 실력이 팍 늘었을 때가 있어요. 그때까지 포기하지 말고 계속 풀어야 실력이 늡니다...

별 방법 없이 문제를 많이 풀라고만 하는 글이 됐네요 ㅠㅠ

딱히 공부를 하는데 있어서 비법은 없는 것 같아요 ㅠㅠ

ksc919   4년 전

역시... 수능때 했던 방법과 비슷하군요.

많은 도움이 됐습니다.

알려주신 증명방법을 기점으로, 꾸준히 해보겠습니다 ㅎㅎ

감사합니다 :)

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