[자바] 백준 1669 - 멍멍이 쓰다듬기 (java)

 문제 : boj1669

---

 

필요 알고리즘 개념

• 수학
  
  • 수학적 사고가 필요한 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  얼핏 어떻게 구해야할지 난감할 수 있다. 구해야하는건 '최소'의 일수라는걸 시작으로 생각해보면 좀 더 쉽게 생각해볼 수 있다. 첫째 날과 마지막 날은 항상 1cm 여야 한다. 그렇다면 가장 빠르게 cm를 증가시키면서 차이를 좁혀야 '최소'일수가 가능하다. 가장 빠르게 cm를 증가시키는 방법은, 중간 지점까지는 매일 +1을 하고, 그 이후로는 매일 -1을 하는 것이다.

  그렇다면 일수는 1+2+3+... 형태의 등차수열의 합 형태가 나온다. 그럼 수식을 생각해볼 수 있다. 기본적으로 다음 수식의 조건을 만족하는 최소의 n이 답이 될 것이다. (n(1+n)/2는 등차수열의 합 공식 n(a+l)/2 에서 a는 1로 고정이고 l은 n으로 고정이므로 저렇게 작성되었다. x2는 위 그림처럼 양옆에서 1+2+3+... 가 진행되므로 x2이다.)

  즉, n(1+n)이 x~y 사이의 차이보다 커지는 최소의 n값을 찾으면 된다. 다만 이건 짝수로 된 일자를 찾는 것이고, 홀수로도 도달 가능할 것인데 그건 이따 다시 생각해보자. 아무튼 1차식이므로 n을 바로 구할 수 있겠지만, 난 수학에 약하기도 하고 double형으로 코드 짜는걸 별로 안좋아한다. 그러니 n을 1부터 계속 증가시키면서 확인해보면 된다. 어차피 대강 n^2 >= 2^31 이면 되므로 모든 경우를 다 봐도 n의 최대값은 몇 만 수준일 것이니 그냥 다 봐도 전혀 상관없다.

 

  아무튼 그럼 그렇게 구한 최소의 n*2가 답이 된다. 다만 여기서 하나 더 생각해볼 수 있는데, 정중앙 부분에 하루를 뺄 수도 있다. 예를들어 Y-X가 9 라고 해보자. n이 2일 땐 위 식의 좌변이 6이 되므로 안되고, n이 3일 때는 12이므로 n=3이 가능한 최소의 n값이다. 이걸 풀어써보면 1+2+3+3+2+1 = 12가 되는데, 사실 중간에 하루를 빼서 1+2+3+2+1로 해도 9가 가능하다! 따라서 저 부분을 체크해줘야 한다. n(1+n) - n >= Y-X 라면 2n-1을 출력해주고(중간에 하루 뺌), 그렇지 않다면 2n을 출력해주면 된다.

 

  주의점은 이미 X==Y 인 경우 0을 출력해줘야 한다는 점이다. 

 

---

 

코드 : 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());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        if (x==y) {
            System.out.println(0);
            return;
        }
        for (long base = 1, gap = y-x; ; base++) {
            long sum = base*base+base;
            if (sum < gap) continue;
            System.out.println(base*2+(sum-base>=gap?-1:0));
            return;
        }
    }

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