[LeetCode] 754. Reach a Number

leetcode.com/problems/reach-a-number/

Reach a Number - LeetCode

 

 

## 접근방법

---

이 문제를 전체 탐색을 한다고 생각하면, 2의 지수승이 되므로 전체 탐색은 무조건 TLE를 받는다고 생각하면 된다. 처음 순간에 +1, -1 이후에 +2, -2를 선택하는 과정을 쭉 생각해보면, 탐색해야 하는 노드의 수는 2 * 2 * 2 * 2...가 될 것이다.

 

 

 

target만큼 접근하기 위해서, 어떻게 해야 할까? target보다 작은 이동거리로는 절대 정답을 얻을 수 없다. 따라서, target보다 같거나 오른쪽 이동만을 생각해보자. 오른쪽 이동을 하다가, target보다 크거나 같다면 중지하자. 중지하는 이유는 최소 이동 거리와 관련이 있다.

 

 

 

값이 같다면 정답을 리턴하고 값이 아니라면 필요한 만큼의 - 부호를 붙여줘서 정답을 찾을 것이다. 값이 다를 때, 오른쪽 이동의 일부들을 -로 만들어서 원하는 값을 얻어야 한다.

 

 

 

+1, +2, +3, ... +k라고 생각해보자. 만약에, 값의 차이가 짝수만큼 난다면, 이 집합들의 일부를 변경해서 어떤 짝수든 만들 수 있을까? +1을 만약에 -1로 바꾸면, 총합의 -2가 된다. +2를 만약에 -2로 바꾸면, 총합의 -4가 된다. +k를 만약에 -k로 바꾸면, 총합의 -2 * k가 된다는 것이다. 발생할 수 있는 값의 차이는 k + 1보다 작으므로, 어떤 짝수든 만들 수 있다는 것이 당연하다.

 

 

 

값의 차이가 짝수인 것은 k 스텝만큼 오른쪽으로 이동한 것을, -로 일부 변경시켜주면 정답을 찾는다. 값의 차이가 홀수인 경우는 어떻게 처리할 것인가? 현재 k가 홀수인 경우와 짝수를 생각해보자.

 

 

 

k 스텝만으로 해결이 되지 않으므로, k + 1을 고려해야한다. k + 1스텝까지 고려하면, 당연히 값의 차이도 k + 1만큼 증가한다.

 

 

 

k가 홀수라면, k + 1은 짝수가 된다. 값의 차이(홀수)에 k + 1을 더하면, 여전히 홀수다. 따라서 k + 2 스텝까지 고려해야 한다. k + 2는 홀수이며, 값의 차이(홀수)에 k + 2를 더하면 짝수가 되므로, k + 2 스텝만에 정답을 찾을 수 있다.

 

 

 

k가 짝수라면, k + 1은 홀수가 된다. 값의 차이(홀수)에 k + 1을 더하면 짝수가 되므로 k + 1까지만 고려하면 된다.

 

## 해설코드

---

class Solution {
    public int reachNumber(int target) {
        int copy = Math.abs(target);
        int step = 0;
        
        while(copy > 0){
            copy -= (++step);
        }
        
        return copy % 2 == 0 ? step : step + 1 + (step % 2);
    }
}