hwy16016   8일 전

풀고나서 고수님들의 코드를 보며 깔끔하게 분할이 가능하다는 것을 깨달았습니다. https://www.acmicpc.net/source...

k가 홀수일때는 짝수로 만들어주고 짝수일 때는 k-n, (n, k/2)를 비교하는데,

k가 홀수일때는 어차피 짝수로 만들면서 +-1을 하기 때문에 굳이 k-n을 할 필요가 없고 모든 케이스가 커버된다는 것을 알 수 있습니다.


Q1. 이런 내용을 수학으로 어떻게 증명할 수 있을까요?

추가로 배수가 3일 때는 함수를 아래처럼 구현했습니다.

배수가 2일 때와 비슷하게 k가 3의 배수가 아닐 때 -k%3을 하거나 +(3-k%3)을 해서 3의 배수로 만들어줍니다.

그런데 k가 3의 배수가 아닐 때 저 두 경우만 비교하면 모든 경우가 커버되지 않습니다.(n=4, k=5)

이런걸 수학적으로 접근하면 좀 더 쉽게 발견할 것 같은데 접근 방법을 모르겠네요..

Q2. 풀이 방법을 구상할 때 수학적 모델?같은 걸 어떻게 세울 수 있나요?(문제 많이 풀어보는 것 말고 좀 정형화된 접근방식같은게 있나요?)

sonjaewon   7일 전

으잉? 저게 Accepted 받는다고여?

전 BFS 로 풀었는데...

이렇게 간단한진 전혀 몰랐네요 신기

hwy16016   7일 전

@sonjaewon

저도 bfs로 풀고 저 코드를 봤습니다. 재귀로 구현해서 정말 예쁘게 구현이 되는 것 같네요

여담으로 이 문제에서는 n이 작아서 별 차이가 나지 않지만, n이 커진다면 저 방법보다 bfs가 평균실행시간이 짧지 않을까 싶네요 ㅋㅋㅋ

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