백준 12966 자바 - 턴 게임 2 (BOJ 12966 JAVA)

문제 : boj 12966

 

 

  수학적인 문제는 좀 피했었는데 오랜만에 도전한건데 잘 풀어낸 것 같아 기쁨. 사실 문제만 보고는 감이 잘 안왔었는데, 일단 주어진 부분에 대해 생각나는 것 부터 차례대로 쳐내다보니 답을 구할 방법이 보였다.

 

1.

일단 n번째(문제에서 'i'로 설명한걸 글에서는 'n'으로 표현한다. 'i'로 글쓰면 1이랑 헷갈린다.) 턴에 승리한 사람이 얻는 점수는 2n-1이다. 만약 n = 5라고 한다면 아래와 같이 된다. 즉, 점수는 모든 홀수인 셈이다.

 

 

2.

우선 불가능한 경우부터 예외처리를 해보자. 문제에서 제시된 게임은 1번째부터 순서대로 계속 진행을 해야 하고, 중간에 둘 다 점수를 못얻는 경우가 없다. 따라서 x와 y를 더한 값이 홀수의 등차수열 합과 일치해야 가능한 경우이다. 뭔소리냐면, 예를들어 x+y가 15라고 해보자. 해당 숫자는 1부터 홀수들을 더해갈 때 만들 수 없는 숫자이다. 따라서 불가능한 경우이므로 -1을 출력하면 된다. 그럼 이걸 어떻게 구할지 수식으로 보자.

 

일단 등차수열의 합 공식은 다음과 같다.

이 문제에서 a = 1로 고정이고, l은 2n-1 이었으며 x+y가 1부터 홀수들을 더한 합이어야 하므로 아래와 같이 볼 수 있다.

위를 정리해보면 아래와 같은 식이 나온다.

  이 때, n, x, y 는 모두 정수여야 하므로 x+y를 square root(이하 sqrt) 한 값이 정수인지 파악하면 x+y가 가능한 경우인지 볼 수 있다. 근데 자바에서 Math.sqrt의 결과는 double형이고, 뭐 sqrt 결과가 53434.00000000001 이런식일 수도 있다. 따라서 안전하게 정수형으로 검증할 방법이 필요하다.

 

  알고리즘 짤 때 소수점 오차를 무시하는 가장 안전한 방법은 어떻게든 정수형 연산으로 변경하는 것이다. 이 경우라면 sqrt한 결과값에 대해 소수점 자리를 버린 후 다시 제곱을 해보는 것으로 실수오차 없이 확인 가능하다. 즉, floor(sqrt(x+y)) * floor(sqrt(x+y)) = x+y (x, y는 정수) 인지 확인하면 프로그램에서 실수 오차 없이 정수인지 판단할 수 있다. (코드 12~16 line)

 

 

3.

다음으로 아마 이것때문에 정답률이 21%로 내려갔을 것 같은 예외처리를 해보자. 홀수의 합으로 만들 수 없는 자연수를 확인해보는 것이다. 결론적으로 '2'만 불가능하다. 만약 x+y가 n^2을 만족한다 하더라도, x나 y가 '2'인 경우엔 불가능한 경우이므로 -1을 출력해야 한다.

1 = 1

2 = 불가

3 = 3

4 = 3+1

5 = 5

6 = 5+1

...

 

 

4.

다음으로, 만약 x가 0이라면 1점도 따지 못한거니 그냥 0을 바로 출력하고 끝내면 된다.

 

5.

이제 예외처리가 끝났으니, 최소한의 횟수로 x를 만드는 경우를 살펴보자. '최소'인게 중요한데, 그냥 단순하게 큰 수부터 x에 대입해버리면 된다. 예시와 함께 보겠다.

 

5.1 e.g. '17 8'을 보자. 우선 x+y = 25이므로, n = 5 임을 알 수 있다. 그럼 1,3,5,7,9를 가지고 이 중 최소한의 홀수를 사용하여 x인 17을 만들어야 한다.

n=5일 때부터 시작해서 n=1일때까지 내림차순으로 확인하면서 빼나가면 된다.

->  17 - 9 = 8

-> 8 - 7 = 1

-> 1 - 5 = 음수이므로 불가

-> 1 - 3 = 음수이므로 불가

-> 1 - 1 = 0

 

-> 즉 17은 최소 3번으로 표현 가능하다.

 

 

5.2 e.g. 그럼 이번엔 '18 7'을 보자. 

x+y는 마찬가지로 25이므로 n = 5 이다.

-> 18 - 9 = 9

-> 9 - 7 = 2

-> 2..?

-> 2-1 = 1 까지 밖에 안된다.

 

여기가 문제이다. 2는 '3.' 에서 확인했듯이 만들 수 없다. 하지만 이 경우엔 좀 다르다.

어떠한 홀수를 뺏을 때 2가 남았다면, 해당 홀수를 사용하지 않고 그보다 작은 홀수 2개를 써서 해당 수를 무조건 만들 수 있다. (즉, 7+1[+1]은 불가능하니 대신 5+3+1을 하면 된다. 확인해보면 모든경우에 적용 가능하다.)

위의 경우 7을 쓰지 않고,

-> 9-5 = 4

-> 9-3 = 1

-> 1-1 = 0

 

이렇게 할 수 있다.

그럼 정리하면, n부터 2까지(실제 값으로 치면 2n-1부터 3까지) 그리디하게 빼나가다가 나올 수 있는 경우는 다음과 같다.

 

A. 0이 남은 경우 -> 답을 찾은 것이니 횟수를 바로 출력

B. 1이 남은 경우 -> n부터 2까지 사용했으므로 1은 항상 남는다. 따라서 1만 더 쓰면 되므로 횟수+1을 출력

C. 2가 남은 경우 -> 해당 수를 사용하지 않고, 그보다 작은 홀수'2'개를 사용하면 되므로, 횟수+2를 출력

 

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long x = Long.parseLong(st.nextToken());
        long y = Long.parseLong(st.nextToken());

        int sqrt = (int) Math.sqrt(x+y);
        if (1l*sqrt*sqrt != x+y) {
            System.out.println(-1);
            return;
        }
        if (x == 2 || y == 2) {
            System.out.println(-1);
            return;
        }

        if (x == 0) {
            System.out.println(0);
            return;
        }

        int cnt = 0;
        for (int i = sqrt; i >= 2; i--) {
            long score = 2*i-1;
            if (x >= score) {
                x -= score;
                cnt++;
            }
            if (x <= 2)
                break;
        }

        System.out.println(cnt+=x);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}