[BAEKJOON] 11561 징검다리

문제 요약

• 알고리즘 분류: 이진 탐색, 수학
• 난이도: Silver3
• 문제내용:
  • 1번부터 N개번 징검 다리가 있다.
  • 첫 징검다리는 아무대나 점프할수 있다.
  • 그 다음 징검다리는 이전 이동한 거리보다 1이상 더 긴거리로 이동해야 한다.
  • N번 까지 최대 몇번 건널수 있는지 구하여리
  • 첫줄에 케이스 T가 주어지고 각 케이스마다 N이 주어진다.

• 사이트: https://www.acmicpc.net/problem/11561

 

문제풀이

이번 문제에서 최대 징검다리수가 10^16 이다. 이정도 숫자이면 1 부터 10^16까지 탐색하면 시간초과가 나올것이다. O(N) 탐색이 아닌 O(logN)의 탐색으로 처리할수 있도록 해야 시간복잡도 문제를 해결할수 있다. 그래서 이번 문제는 이진 탐새으로 풀어야 할수 있다. 이진 탐색 관련글은 아래에서 확인 해보면 된다.

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

이진 탐색

문제 접근 방법

  이진 탐새을 어떻게 구현할까 하기 전에 알아 되는것이다. 다시 문제의 내용을 보면 

1. 처음에 아무대나 이동 할수 있다.
2. 다음 이동 할때 이전 이동한 수에서 +1 이상 움직어야 한다.

이렇게 보면 최대 건너 갈라면 처음에 1 만큼 움직어야 하고 그 다음에는 2, 3, 4, 5 만큼 이동 해야 최대로 건너 갈수 있다. 그럼 건너가는 횟수를 K라고 하면  K에서 1 부터 K까지 더한것 결과 값이 징검다리 개수와 비교 하면 된다. 

 일단 1 부터 K까지 반복문으로 구현하면 그 만큼 연산 횟수가 늘어 나기 때문에 아래의 시그마의 공식을 사용 해서 구현 하면된다.

 

그 다음에는 이분 탐색을 통해 K 값을 찾아가는 방식으로 문제를 풀어갑니다. 여기서 이분 탐색은 lower bound 방식으로 구현히먄 된다. 다시 말해, K가 이동한 징검다리 수 이상인 값들 중 가장 작은 값을 구하는 것이 목적이다.

2. 이분 탐색 구현 방식

1. 초기 설정
   이분 탐색을 시작하기 위해 start는 1로, end는 주어진 징검다리 수로 설정합니다. 이렇게 start와 end를 좁혀가며 탐색할 수 있다.
2. 중간 값 계산
   이분 탐색의 일반적인 방식대로 start와 end의 중간 값을 구한다. 그 중간 값 기준으로 1부터 중간 값까지 징검다리를 더한 값과 실제 징검다리 수를 비교하여 다음과 같은 과정을 거친다.
   • 조건 확인 및 값 갱신
     • 중간값까지의 합이 징검다리 수 이하일 경우:
       • start를 중간 값 + 1로 설정하고, 중간 값을 별도로 저장한다.
       • 결과 값을 별도로 두고, 초기에는 0으로 선언한 후 중간 값과 비교하여 큰 값을 저장해둡니다. 이는 나중에 중간 값이 더 적을 경우를 대비하기 위함이다.
     • 중간 값이 징검다리 수를 초과하면:
       • end를 mid - 1로 설정하여 탐색 범위를 줄여나간다.

start가 end랑 같을때 까지 탐색하고 결과값을 출력만 하면 끝이다.

설명으로는 이해하기가 힘들수 있어서 예제  100기준으로 설명하겠다.

징검다리 개수 100
1. start = 1, end = 100, mid = 50
1 부터 50 합 → 1,275
100보다 크기 때문에 end를 49로 줄인다.
2. start = 1, end = 49, mid = 25
1 부터 25 합 → 325
100보다 크기 때문에 end를 24로 줄인다.
3. start = 1, end = 24, mid = 12
1 부터 12 합 → 78
100보다 작기 때문에 start를 13으로 늘린다.
4. start = 13, end = 24, mid = 18, result = 12
1 부터 18 합 → 171
100보다 크기 때문에 end를 17로 줄인다.
5. start = 13, end = 17, mid = 17
1 부터 17 합 → 153
100보다 크기 때문에 end를 16로 줄인다.
6. 5. start = 13, end = 16, mid = 15
1 부터 15 합 → 120
100보다 크기 때문에 end를 14로 줄인다.
7. 5. start = 13, end = 14, mid = 13
1 부터 13 합 → 91
100보다 작기 때문에 start를 14으로 늘린다.
 mid값이 이전 result보다 커서 result를 13으로 저장한다.
8. 5. start = 14, end = 14, mid = 14, result 13
1 부터 14 합 → 105
100보다 크기 때문에 end를 13로 줄인다.
9. start가 end보다 크기때문에 이분탐색 종료하고 결과값을 13으로 출력한다.

마무리

위에 정리하면 아래와 같다.

1. start를 1로 지정하고 end를 징검다리수로 지정한다. 결과를 저장하기 위해서 결과값을 0으로 초기화 한다.
2. start가 end보다 클때 까지 이분 탐색한다.
3.  1부터 mid 더하고 아래 조건에 따라 처리한다.- 더한 합이 징검 다리 보다 작으면 start를 mid +1로하고 mid값을 기존 결과값보다 크면 저장한다.
   - 더한 합이 징검 다리 보다 크면 end를 mid - 1로한다.

 위와 같이 구현했을때 시간 복잡도는 O(logN)만큼 나온다. 

이번문제에서는 내가 놓친 부분은 아래와 같다.

1. 최대 숫자가 10 ^ 16승것
2. 이진 탐색하면서 중간에 결과를 저장안함 점

Code

Python

import sys
import math
input = sys.stdin.readline

for _ in range(int(input())):
  N = int(input())
  # 10 ^ 16승 부터 수열 합구하면 Long 타입 벗아나서 N보다 범위 좁혀야 한다.
  # 수열의 계산 따르면 답은 (2 * N) ^ 0.5 안에 있어서 end를 (2 * N) ^ 0.5로 한다.
  start, end = 0, int(math.sqrt(2 * N + 1))
  result = 0
  while(start <= end):
    mid = (start + end) // 2
    # 이전 징검다리 이동한 수에서 최소 한칸더 움직인다면 N 수열의 합으로 체크 한다.
    count = mid * (mid + 1) // 2
    if(count <= N):
      start = mid + 1
      # 이전 mid가 범위가 더 작아 질수 있으로 이전 result과 비교해서 최대 값을 넣는다.
      result = max(result, mid)
    else:
      end = mid - 1
  print(result)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long T = Long.parseLong(br.readLine());
		for (int i = 0; i < T; i++) {
			long N = Long.parseLong(br.readLine());
			long start = 0;
			// 10 ^ 16승 부터 수열 합구하면 Long 타입 벗아나서 N보다 범위 좁혀야 한다.
			// 수열의 계산 따르면 답은 (2 * N) ^ 0.5 안에 있어서 end를 (2 * N) ^ 0.5로 한다.
			long end = (long) Math.sqrt((2*N + 1));
			long result = 0; // 결과를 저장하는 변수
			while (start <= end) {
				long mid = (start + end) / 2;
				// # 이전 징검다리 이동한 수에서 최소 한칸더 움직인다면 N 수열의 합으로 체크 한다. 
				long count = mid * (mid + 1) / 2;
				if(count <= N){
					start = mid + 1;
					// # 이전 mid가 범위가 더 작아 질수 있으로 이전 result과 비교해서 최대 값을 넣는다.
					result = Math.max(result, mid);
				}else{
					end = mid - 1;
				}
			}

			System.out.println(result);
		}
	}
}