첫번째 풀이 241227
-
재귀로 풀었는데 4퍼센트 발생했다.
-
반례
: 최악의 경우를 생각해보자.
숫자버튼 023456789 가 고장나버린 상태다. 1만 사용가능한 상태다.
그 가운데 이동하고 싶은 채널 번호가 888 이다.
초기값 100번에서 888로 이동하는데는 788번이다.
1만 사용가능하므로 1111 로 간 다음에 1111 - 888 하는 것이
100번에서 888번으로 이동하는 것보다 최소의 비용이다. -
즉 나의 시퀀스로는 이동하고자 하는 채널의 동일한 자릿수만큼만 진행하므로
도저히 불가능한 시퀀스이다.
-> 재귀로 풀기에는 위의 쉽게 생각할 수 없는 뜻밖의 조건들에 관해서도 신경써야 한다.
돌아보기
: 어떻게 접근하는 것이 쉽게 풀 수 있을까?
1) 반드시 숫자버튼을 누른 다음에 플러스를 하거나 마이너스를 해야 한다.
이동 want : 5248
시작 : ++++하고 숫자 입력 5247 그 다음에 +
-> 라고 한다면 앞에 입력한 ++++ 는 아예 불필요한 값이다.
2) 플러스와 마이너스가 함께 사용할 필요가 없다.
최소값이 되지 못하기 때문
wnat : 5248
start : 5247 ----++++
-> 불필요하다.
어떻게 풀것인가???
: 숫자버튼을 일단 먼저 누른후, 플러스나 마이너스를 하나만 선택해서 몇번 누를것인가? 이다 그러면서 해당 want 채널 번호로 최소한의 카운팅수로
갈수 있는지를 구하는 것이다.
-
숫자버튼으로 어떤한 번호를 만들지는 알수 없다는 것이다.
: 브루트포스 문제는 어떠한 방법을 행하라, 그런데 알수 없다는 정보는 모든 방법을 총동원해서 돌려서 다해보라는 것이다. -
첫번째 풀이에서 별다른 생각없이 재귀로 갔지만, 위의 고찰을 통해서 브루트포스로 풀어야 겠다고 생각했다면 재귀보다 더 쉬운 브루트포스로 가야 한다!
힌트
: 문제의 예시를 보면, 이동하고자 하는 채널의 번호는 50만인데,
예제 3번을 보면, 511111로 이동후 나머지는 뺀값인 11111 만큼 누르는 것이 최소 비용이다. 즉 숫자를 누를 때 범위 50만을 넘겨도 된다는 것이다.
그러면 숫자를 누를 수 있는 범위는 어떻게 될까???
정말 중요한 부분
: 범위 정하기
1) 최악의 경우를 생각해보자.
want : 50만 그런데 숫자버튼 전부다 고장인 상태다.
100 에서 50만 go : 이 때는 49만 9900 (최대값이다.)
2) 위로 시작버튼을 낮게 눌러서 올라가는 경우에 대해서만 생각했는데, 힌트를 통해서 시작버튼을 아예 높게 눌러서 want 값으로 마이너스 하는 방법도 있었다.
최악의 경우를 생각해보면, 1)번에서 구한 49만 9900번 을 이용하는 것이다.
-
이러한 방법이 있다.
want : 50만
플러스를 49만 9900번 누른 만큼 이번에는 마이너스를 49만 9900번 누를 수 있는 경우를 만든다면 시작 버튼은 99만 9900 번이다.
-> 계산하기 불편해서 100만으로 처리한것이다.. -
우리가 범위를 정하는데 있어서 정확한 값을 선정할 필요가 없다.
모든 경우를 돌려야 하고, 그 가운데서 최대값을 100만으로 지정한 것일 뿐이다.
