728x90
두 가지 규칙을 이용하여 목적지까지 가는 문제.
1. 점프 - 1만큼 건전지 소모
2. 순간이동 - 현재 위치의 2배인 곳으로 이동, 건전지 소모 x
=> 건전지 소모를 최소로 하여 목적지까지 도달?
=> 역행추론이 필요한 문제.
ex ) 목적지 - 250
250은 125에서 순간이동
125는 124에서 1만큼 점프
124는 62에서 순간이동
62는 31에서 순간이동
31은 30에서 1만큼 점프
30은 15에서 순간이동
15는 14에서 1만큼 점프
14는 7에서 순간이동
7은 6에서 1만큼 점프
6은 3에서 순간이동
3은 2에서 1만큼 점프
2는 1에서 순간이동
1은 0에서 1만큼 점프
따라서 총 소모되는 건전지는 6.
위 과정을 코드로 나타내면 되는데,
이 코드는 신기하게도 목적지 값을 이진수로 표현했을 때의 1의 개수이다.
(250 = 11111001(2))
'programmers' 카테고리의 다른 글
| [C++ Programmers 2021 Kakao Blind Recruitment - 메뉴 리뉴얼] (0) | 2022.04.17 |
|---|---|
| [c++ programmers 모음사전] (0) | 2022.04.02 |
| [c++ programmers level1 - 소수 찾기] (0) | 2022.03.31 |
| [c++ programmers 정렬 - 가장 큰 수 ] (0) | 2022.03.31 |
| [programmers 오픈채팅방 c++] (0) | 2022.03.15 |
