[BaekJoon/백준] 1011번 풀이

멀고도 험했던 1011번. 내가 다양한 코딩문제를 보면서 이렇게나 정신적으로나 시간적으로나 소모가 많았던 것은 처음이였다.

말 그대로 벽을 느꼈다. 그것도 엄청나게 높은 벽.... 뭔가 내가 해결할 수 있을 거라는 엄두가 나지 않는 벽 말이다.

 

아직도 나는 수학울렁증이 있는 것 같다. 아니 수학 기피증도 있는게 확실하다.. 문제를 읽다가 수학적인 말이 나오면 잠시 딴생각에 빠진다. 그리고 정신차리면 문제를 처음부터 다시 읽어야 하는 상황. 정말 몹쓸 짓이다.

 

문제를 읽는데 이번에는 규칙을 찾기 위해 숫자를 나열하는 데에도 엄청나게 틀려댔다. 횟수에 따른 규칙을 찾으려고 나열을 하는데도 돌아보면 틀리는 것이다. 그냥 수학적 머리가 아예 없나보다. 집중도 못하는 것 같고.

 

여튼 공식을 내리다보면 또 숫자들 사이에서 정신이 혼미해진다. 뭘 해야할지도 모르겠고 두려움이 앞선 그런느낌.. 이 문제의 경우를 나열하다가 문득 이걸 어떻게 풀지 라는 생각이 들었고, 규칙을 찾아내는 과정도 거의 없었다. 그냥 숫자만 들여다보며 시간만 쓴 느낌.. 정신은 저 멀리에...

 

그래서인지 도중에 포기하고 다른 사람들의 코드를 찾아봐도, 설명을 읽어봐도 온통 복잡한 수학적 계산과 뭉텅이의 코드들을 보고 울렁거리기만 하고 코드를 제대로 들여다 보지도 못했다. "규칙이 x가지이고 그 규칙에서 첫번째 규칙은 x의 제곱일때 이렇고.. 두번째 규칙은 이런 경우엔 저럴 때와 저럴 때... 제곱하고 곱하기 2에 마이너스1.." 이런 설명들을 보며 내 기준에서 너무 어렵고 복잡한,, 내 집중력과 이해력 이상을 요구하는 해설들은 내 벽을 더 높게 쌓아만 갔다...

 

그러다 문득 친구가 "수학이라고 생각하지말고 규칙을 찾는 문제라고 생각해. 수학이라고 하면 거리감과 울렁증이 반사적으로 나오는게 문제해결에 도움이 못되는 것 같다" 라는 말을 해주고 힘이 생겼다. 그리고 말그대로 '수학' 이 아닌 '숫자'의 관점에서 문제에 쉽게 접근할 수 있는, 아니 어쩌면 모든 문제에는 쉽게 접근하는 방법이 있다. 따라서 이 규칙이 어떻게 이루어지는지에 대해 가장 간단한 정보를 통해 쉬운 관점으로 바라봤다.

 

정말 간단하게 문제를 해결할 수 있다. 천천히 따라오라..

1 : 1
2 : 1 1
3 : 1 1 1
4 : 1 2 1
5 : 1 2 1 1
6 : 1 2 2 1
7 : 1 2 1 2 1
8 : 1 2 2 2 1
9 : 1 2 3 2 1
10: 1 2 3 2 1 1
11: 1 2 3 2 2 1
12: 1 2 3 3 2 1
13: 1 2 3 3 2 1 1
14: 1 2 3 3 2 2 1
15: 1 2 3 3 3 2 1
16: 1 2 3 4 3 2 1
17: 1 2 3 4 3 2 1 1


1 2 3 5 7 10 13 17 마다 길이가 1씩 증가.
1 2 3 4 5 6  7  8

 

17번째까지는 나열해보자. 그러면 위와 같은 규칙을 찾을  수 있다. 바로 1 2 3 5 7 ... 마다 길이가 1씩 증가한다는것.

그리고 그 길이는 바로 아래에 같이 써놨다. 벌써부터 너무 불안해 할 필요 절대 없다. 불안하면 지는거다.

 

우리가 N이라는 수를 입력받았을 때, 그 수가 과연 몇 길이인지 찾는 것이 문제이므로, "1 2 3 5 7 10 13..." 의 규칙을 찾아서

처음부터 돌려주며 N이라는 수와 비교해주면 되지않을까?

 

즉 이 값들이 어떻게 변하는지만 알면 된다.

1 2 3 5 7 10 13 17.... 마다 값이 1씩 증가.

 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8

값들 사이에 값이 어떻게 변하는지 아래에 적어봤다. 이런 식으로 더해지면서 값이 올라가게 된다. 이게 무슨 뜻이냐면, 아래 값들을 더해줄 때 마다 +1 카운트를 넣어주면, 우리가 원하는 '길이' 에 대한 값을 찾을 수 있고, 이렇게 아래 값들을 토탈 값에 계속 더해주면서 도출된 값이 입력 값과 연관이 될때까지 포문을 돌려주면 되는 것이다.

 

다시 항의 번호까지 적어주면

1 2 3 5 7 10 13 17 마다 값이 1씩 증가.
1 2 3 4 5 6  7  8

 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8

이런식으로 된다. 맨윗줄은 1씩 증가되는 숫자 경계, 둘째줄은 항의 번호이자 '길이', 셋째줄은 첫째줄의 증가 규칙이다.

 

1+ (1 + 1) + (2 + 2) + (3 + 3) + (4 + 4) ...
1   2   3     4   5     6   7     8   9  ...

위가 값이 증가되는 방식. 아래가 그 때마다의 길이이다. 즉 저렇게 숫자를 더해주면서, 내가 더해서 만들어 놓은 숫자가 입력받은 숫자보다 크게 될 경우까지 반복해준뒤, 크게 된 경우까지 위에 숫자를 더해줬기 때문에 받은 값 보다 길이가 하나 늘어났을 테니 길이를 하나 빼주면 된다.

import java.util.Scanner;

// x와 y는 int형의 최댓값 미만이므로 상관없는데, value같은 경우는 distance보다 큰 숫자일 때 까지 반복하므로 int형 최댓값을 넘을 수 있으니 long으로 선언해야함 주의.
// ( value가 distance보다 클 때까지 반복해준 뒤
// value의 규칙은 길이가 1씩 늘어가는 숫자의 규칙이므로
// distance보다 value가 커졌을 경우를 찾았을 때 해당 value는 distance보다 길이가 1 많은 상태이므로 
// 1을 빼주면 distance 길이를 출력할 수 있다는 것이 내 코드 )
public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
            int T = scanner.nextInt();
            for (int i = 0; i < T; i++) {
                int x = scanner.nextInt();
                int y = scanner.nextInt();

                long distance = y - x;

                int f = 1, b = 1, count = 1;
                long value = 1;

                while (true) {
                    value += f;
                    f++;
                    count++;
                    if (distance < value)
                        break;
                    value += b;
                    b++;
                    count++;
                    if (distance < value)
                        break;
                }
                System.out.println(--count);
            }
    }
}

 

∙ x와 y는 int형의 최댓값 미만이므로 상관없는데, 내 코드에서 value같은 경우는 한번 더 연산하고(클때까지를 찾기 위해) count에서 한번 빼주는 작업(value는 '길이'가 증가되는 숫자의 규칙이므로)이기에 int형 최댓값을 넘을 수 있으니 long으로 선언.

 

∙ 횟수가 1회 증가하는 값 기준이 1 + 1 1 2 2 3 3 4 4 5 5 6 6..일때 이므로 +할때마다 count값도 늘려가면서 distnace값과 비교하여 몇번째인지 보면됌.

 

2일이 걸렸다....

교훈 : 어렵게 생각하고 어렵게 접근하면 끝도없다.. 규칙에는 간단한 근본이 있다. 그것부터 생각하면 쉬운 접근법이 나올 것..!

그리고 항상 한단계 깊게 들어가기 전에 주어진 환경을 응용하여 접근방법을 한번만 더 생각해보자.