99클럽 코테 스터디 2일차 TIL

백준 - 11561번

문제의 핵심은 2가지로 생각했다.

• 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
• N번 징검 다리는 반드시 밟아야 한다.   

생각만 했지 손도 못댔다.

노트에 징검다리 그림까지 그려가며 풀어봤지만 코드 한 줄 적지 못했다.

작은 수부터 그림을 그려가며 규칙성을 파악하고자 했다.

N	result
1, 2	1
3, 4, 5	2
6, 7, 8, 9	3
10, 11, 12, 13, 14	4

뭐하는건가 싶었다.

 

결국 검색의 도움을 받았다.

---

등차수열

연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다.
이때 두 항의 차이는 이 수열의 모든 연속하는 두 항들에 대해서 공통으로 나타나는 차이므로, 공차라고 한다.
- 위키백과

 

왜 등차수열이 나왔을까.

문제 조건 중, 이전 점프한 거리보다 1 이상 더 긴 거리를 뛰어야 한다고 나와있다.

1칸을 뛰었다면, 다음에는 2칸을, 다음에는 3칸을... 마지막은 k칸만큼의 거리를 뛰어야 한다.

 

징검다리가 9개 있고 마지막 N번 징검다리를 무조건 밟아야 한다고 가정해보자.

• 2칸 - 3칸 - 4칸 -> 9
• 1칸 - 2칸 - 6칸 -> 9

경우의 수는 2가지로, 밟을 수 있는 징검다리의 최대 수는 3개이다.

점프한 거리를 모두 더했을 때 징검다리의 개수와 동일하다.

즉, 등차수열의 합이 징검다리 개수와 같아야 된다는 것이다.

 

하지만 2, 3, 4는 등차수열이지만 1, 2, 6은 등차수열이 아니다.

그리고 승택이가 처음에 1칸을 뛸지 2칸을 뛸지 특정할 수 없다.

 

무조건 1칸을 먼저 뛴다고 가정하고 등차수열이 되기 위해서는

1,2,3 이 되어야 하지만 등차수열의 합이 9보다 작으며, 4를 더하게 되면 9를 넘어가버린다.

합이 작든 크든, 마지막 N번 징검다리를 밟지 못한다.

9보다 작은 상태에서 조건이 성립되기 위해서는 마지막 3을 6으로 바꿔주면 된다.

 

문제는 몇 번째 징검다리를 밟아야 하는지가 아닌 그저 최대 수를 구하는 것이므로,

마지막 수를 치환하는 작업은 고려하지 않아도 된다.

 

결국, 특정 값에 대한 등차수열의 합이 N보다 작거나 같아야하며, 작다면 그중 최대값을 찾으면 된다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            long n = sc.nextLong();
            
            long result = 0;
            long start = 0;
            long end = Integer.MAX_VALUE;

            while (start <= end) {
                long mid = (start + end) / 2;
                long sum = (mid * (mid + 1)) / 2;

                if (sum <= n) {
                    result = Math.max(mid, result);
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            sb.append(result).append("\n");
        }

        System.out.println(sb);
        sc.close();
    }
}

 

입력 범위가 크기 때문에 반복문으로 구현하게 되면 시간 초과가 발생할거라 생각되어, 이분탐색을 사용하여 구현했다. 

---

알고리즘 문제는 그냥 맞는 알고리즘만 적용하면 풀어지는 줄 알았다.

본질적인 문제는 해결하지 못하고 키워드 힌트의 알고리즘을 적용해볼 생각만 하니 풀어질 리가 없다.

 

문제 해결력이 정말 많이 부족하다.

쉬운 문제부터 해결해나가도록 하자.

 

백준11561번 징검다리

https://www.acmicpc.net/problem/11561