28857 Морской бой(해전) (백준, python3)

 

시간 제한	메모리 제한
2초	1024MB

문제

(본문이 러시아어이기 때문에 번역 결과만 간단히 요약함)

1*n 크기의 필드가 주어졌을 때 k크기로 배를 배치하는 방법은 1*k 크기의 배를 1척, 1*(k - 1) 크기의 배를 2척, 1*(k  - 2) 크기의 배를 3척, ..., 1*2 크기의 배를 (k - 1)척, 1*1 크기의 배를 k척 띄우는 것이다. 배는 서로 겹쳐지거나 공백 없이 맞닿아 있을 수 없다. 주어진 필드 내에서 배치 가능한 최대 k를 출력하시오.

 

입력

한 줄로 n이 주어지며 필드의 가로 칸 수를 나타내는 정수이다.

(0 ≤ n ≤ 1e18)

 

출력

조건에 맞춰 필드에 배치 가능한 최대 k를 출력하시오.

 

---

풀이

식 세우기가 좀 까다로웠다.

우선 배의 전체 길이만 더해보면 이런 식으로 정리된다.

1 * k + 2 * (k - 1) + ... + (k -1) * 2 + k * 1
= 1 + (1 + 2) + (1 + 2 + 3) + ... + (1 + 2 + ... + k -1) + (1 + 2 + ... + k)

그리고 배와 배 사이의 공백은 전체 항 개수에서 1 뺀 값이다.

 

식만 세우면 이제 나머지는 이분 탐색으로 해결이 가능한데, 그 이유는 n의 범위가 정신 나가버렸기 때문

 

임의의 k를 정해서 k개의 배를 놓을 수 있는 최소 칸 수를 F(k)라고 했을 때, F(k) > n라면 k를 줄여야 한다. 아니라면 k를 늘려봐도 된다. 엄밀하게는 F(k)가 n을 초과하지 않는 k를 구해야 한다. 그러니까, 이분 탐색 중에서도 정확한 값이 아닐 때 마지막 탐색 위치의 왼쪽 값을 내놓는 이분 탐색이어야 한다.

 

 

정답 코드

import sys
input = sys.stdin.readline
def solution():
    n = int(input())
    s, e = 0, n + 1
    while s < e:
        m = (s + e + 1) // 2
        
        # 식 정리하면 이렇게 됨
        if m * (m + 1) * (m + 5) // 6 - 1 <= n:
            s = m
        else:
            e = m - 1
    print(e)
solution()