mym0404   2년 전

블로그 에 설명은 해두었는데 문제를 풀때는 직감적으로 느꼈던거 같은데 막상 증명해보려니까 이렇게 하는게 맞는지 좀더 단순하게 풀어말할 수 있는지 궁금합니다.

----------------

마지막에 컨븨를 3번 이하로 해야 가장 최대라고 귀납적으로 식을 세워보겠다.

k(1)

일단 n = 1 일때는 당연히 컨븨를 할 횟수가 안되므로 성립한다. n <= 6 일때까지 모두 버튼 클릭 횟수가 반환되기 때문에 문제없다.

k(n) -> k(n + 1)

K가 있는 상태에서 선택, 복사, 붙여넣기 4번으로 로 4K를 만들어보자.

4K를 만드는데 선택 1, 복사 1, 붙여넣기 4가 든다.

총 6번으로 4K를 만든 것이다.

그런데 K 일 때 복사되어 있는 값의 최소값은 K/3 일 것이다. 왜냐면 귀납적으로 식을 세웠기 때문에 이전에도 최대 3번만 복사해서 K가 나왔을 것이기 때문이다.

그런데 이 상태에서 붙여넣기 1(K/3) 선택 1 복사 1 붙여넣기 3(4/3K * 3)을 하기만 해도 6번만에 4K가 된다.

K만 있는 상태에서 이전에 복사한 횟수가 1회나 2회로 더 적었다면 6번이면 4K 보다 더 커진다.

그러니까 결론적으로 붙여넣기 4번이 나올일은 절대 없다.

-----------------

감사합니다.

cnh0214   2년 전

감사합니다. 저는 일일이 손으로 직접 계산해서 붙여넣기 세 번까지만 생각해서 값을 도출해냈는데 증명까지 해주셨군요!


블로그 내용 잘 봤습니다!

mym0404   2년 전

네 봐주셔서 감사합니다 ^^

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