23978. [Python]급상승

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 512MB
• 이분 탐색

 

3. 파이썬 코드

 

N, K = map(int,input().split())

days = list(map(int,input().split()))
# 시작 값
start = 1
# 끝 값 구하고자 하는 돈
end = K
# 이분 탐색
while start <= end:
    # 돈의 총합 계산
    total = 0
    # 중앙 값
    cost = (start + end)//2
    # 일수 만큼 반복문 진행
    for i in range(1,N):
        # 일수 차이가 얼마나 나는지 체크하는 변수
        check = days[i] - days[i-1] -1
        # 중앙 값이 일수 차이보다 작은경우 중앙값은 무조건 1까지 내려가기 때문에 N 부터 1 까지 합 공식 적용
        if cost <= check:
            total += cost * (cost+1) // 2
        # 중앙 값이 일수 차이보다 큰 경우 M 부터 N 까지 값을 구하는 공식 적용
        else:
            total += (cost+(cost-check)) * (cost-(cost-check)+1) // 2
    # 반복문이 끝난 후 마지막 값에 대해서 N 부터 1 까지 공식 적용
    else:
        total += cost * (cost+1) // 2
    # 더한 값이 K 값보다 크거나 같은지 체크
    # 큰 경우 end 값을 갱신하여 값의 범위를 줄임
    if total >= K:
        end = cost - 1
    # 작은 경우 start 값을 높여 값을 높임
    else:
        start = cost + 1
print(start)

 

4. 문제를 풀고난 후 생각

 

• 문제를 읽고 숫자의 범위가 너무 커서 이분 탐색 방법을 고민했고 어떤 값을 가지고 이분탐색을 진행할지 생각을 많이했던 문제이다.
• 결국 K 값의 돈을 넘기면 되기 때문에 K 값을 끝점으로 잡고 이분 탐색을 진행했다.
• 돈의 총합은 cost(mid) 값과 check(일수차이)를 비교하여 일수 차이가 더 큰 경우 1부터 N 까지 합을 구하는 점화식을 사용했고, 그 외의 경우 M부터 N 까지 합을 구하는 점화식을 사용했다.
  
  

● 1부터 N 까지 합을 구하는 식 => S = (N) * (N+1) // 2

● M부터 N 까지 합을 구하는 식 => S = (M+N) * (M-N+1) // 2 (M이 더 큰 수로 가정)

 

• 위 계산을 다 하고 한번 더 N부터 1 까지 합을 구하는 식을 더해준다. 마지막 일수의 값이 계산에서 누락됐기 떄문에

 

5. 문제를 푸는데 도움이 되는 지식

 

• 이분 탐색