문제

[프로그래머스] 점프와 순간이동

---

접근방법

가장 효율적인 방법

1. 이 문제는 가능한 2배수로 움직여야 한다
2. 2배수로 움직일 수 없다면 1칸을 움직인다

가장 효율적인 것은 마지막에 뛰는 것이다

---

2배수일 때와 아닐 때

그렇다면 가장 마지막에 2배수로 뛰어서 도착했다고 가정한다
2배수가 아니라면 2배수로 뛰고 부족한 칸을 점프해서 왔다고 생각한다

2배수가 아니라면 그만큼 뛰기

2배수라면 그 값을 1/2해주기

위와 같은 논리를 계속 반복한다

---

해결

#include<iostream>
using namespace std;

int solution(int n) {
	int ans = 0;
	while (n > 0) {
		if (n % 2 == 0) n /= 2; // 2로 나눠진다면 2로 나눈다
		else {
			n -= 1; // 2로 나눠지지 않는다면 2로 나눠질 때까지 뺀다 
			ans++;  // 2배수로 움직이는 게 빠르므로 2배수가 될때까지만 건전지를 쓰며 전진하는 것
		}
	}
	return ans;
}

참고블로그

• 위 블로그를 보고 해결했습니다

---

어려웠던 부분

풀기 전에 겁을 먹었다
내가 약한 문제가 여러가지 조건들 중에 하나를 선택하는 것이다
따져야 할 조건들이 많게 느껴질 때 어떤 것을 기준으로 삼아야 하는지 잘 모른다

여러가지 문제를 풀면서 느끼는 것은
논리의 본질, 해결해야 하는 문제들 사이의 공통점을 먼저 파악하는 것이 중요하다는 것이다
구현에 많은 시간을 들이기 전에 핵심적인 구조를 파악해야 한다

많은 문제들이 보기에 복잡해보여도 핵심논리를 파악하면 구조가 깔끔해진다