[백준 12934번] 턴 게임 - java

문제 설명

1. 숫자 x와 y가 주어진다.

2. 턴은 1부터 시작하고, n번째 턴의 승리자는 n점을 얻는다.

3. x와 y에 대해 각각의 점수를 얻는것이 불가능하면 -1출력

4. 가능하면, x점수를 얻는 최소한의 승리횟수를 구하면 된다.

 

풀이 과정

 1. 1, 2, 3, 4, 5, 6, ..... 의 점수를 얻는 방법은 (N*(N+1))/2 이다. 이것만 알면 간단하다.

 2. 사실상 수학적 구현 문제이다.

 3. 참고로 이거 숫자가 long형식이니까 주의하자.

 4. 이를 생각하고 풀이과정을 도출해보자

---

A. x와 y의 합계점수에 대해, 여기 정확히 도달할 수 있어야 한다. 해당 숫자보다 작으면 그보다 큰 숫자로 (N*(N+1))/2을 시도하고, 만약 이게 x+y보다 크면 불가능할것이다.

B. (N*(N+1))/2으로 구한 N에 대해 정확이 x+y이면 답을 구할 수 있을 것이다.

C. 구해온 N부터 아래로 하나씩 내려가며 x에서 빼준다. 큰 수부터 빼주면 당연히 최소횟수를 구할 수 있다.

-> 위의 C번 로직에 대해, 큰 수부터 뺐을 때 x가 정확히 0이 되지 않고 음수가 되지 않나? 싶을 수 있지만 사실 최소의 횟수를 구하는 것이므로 구해진 숫자가 당장 음수인지 아닌지는 상관이 없다.

-> 예를 들어 x=6, y=9라고 가정해보면 N은 5이다.

그럼 C의 로직을 시행하면

1. x -= 5    -> x = 1

2. x -= 4    -> x = -3

이렇게 되는데, 어차피 5를 빼고 1을 빼주는 로직 자체도 당연히 4보다 아래에 있으므로 가능하다는 것이다.

즉 1은 4보다 밑에 있으니까 4로 가능하면 1은 당연히 가능하고 이는 최소횟수에 해당하므로 가능한 것이다.

이건 그리디를 풀 때에 굉장히 중요한 풀이이므로 기억해두는것이 좋을것이다.

---

 

코드