[파이썬] 백준 28257: 알록달록 초콜릿 만들기 (골드3)

[파이썬] 백준 28257: 알록달록 초콜릿 만들기 (골드3)

 

28257번: 알록달록 초콜릿 만들기

---

문제

---

풀이

0. 방향성 생각

태그는 이분탐색인데 계차수열 보다보니까 바로 점화식 나와서 점화식으로 풀었다.

계차수열 구하면

<4 2> <3 3>

<4 3 2> <3 3 3 3>

<4 3 3 2> <3 3 3 3 3 3>

이런식으로 나온다.

계차수열이 4가 되는 지점을 찾고 거기서 부터 얼마나 떨어져 있는지를 계산한다.

4가 되는 지점을 a0, a1, a2 ...이라 하면

a0 = 1, a1 = 3*4 + a1, a2 = 3*7+a2 ...

즉, an = 9n+3 + an-1이다. bn = an-an-1 = 9n+3

sigma bn = an-a0이고 an = sigma bn + a0이다.

따라서 an = 3n(3n+5)*0.5 + 1이다.

 

계차수열이 4가되는 지점을 모두 구할 수 있고 그 지점으로부터 얼마나 떨어졌는지 수열의 규칙을 통해서 찾을 수 있다.

또한 계차수열에서 다음 4가 나오기까지 규칙은 4개,7개,10개 ... 즉 3n+1개임을 알 수 있다.

이를 누적해서 현재 4가 나오는 지점의 인덱스를 구할 수 있다. f(k) = sigma 0 to k 3n+1 = 0.5 * k(3k+5) + 1이다.

 

f(0) = 0, f(1) = 5, f(2) = 13 ... 이런식으로 계차수열이 4가 되는 지점의 인덱스를 구할 수 있다.

역함수를 구하면 k번째 민트초코가 들어왔을 때 어느 범위에 있는지 확인할 수 있다.

def checkpoint(k):
    return int(((1/3)*(2*k+1/12))**0.5-5550/6666)

원래 마지막에 -5/6인데 k가 작을 때 부동소수점 오류가 발생해서 이를 처리해준다.

입력이 들어오면 몇 번 째 체크포인트 다음에 등장하는지 알 수 있다.

 

예를 들어서 checkpoint(34)를 넣으면 4번 째 체크포인트가 나온다. (1,5,13,34 ...)

 

def checkpoint_idx(k):
    return int((1/2)*(3*k**2+5*k)+1)

또한 checkpoint의 인덱스를 구하는 함수로 인덱스를 구한다.

 

def cvt_value(n):
    return int((1/2)*(3*n)*(3*n+5)+1)

앞서 구한 체크포인트를 받아서 값으로 변환시켜준다.

 

for _ in range(int(input())):
    n = int(input())
    cp = checkpoint(n)
    idx = checkpoint_idx(cp)
    d = n-idx

    if d==0 : print(cvt_value(cp))
    elif 1<=d<=cp+1 : print(cvt_value(cp)+4+3*(d-1))
    else : print(cvt_value(cp)+3*d)

n번 째 입력을 받고 체크포인트 함수에 넣어서 어느 범위에 있는지 본다.

체크포인트를 idx 변환 함수에 넣으면 몇 번 째 범위에 존재하는지 나온다.

 

<4 2> <3 3>

<4 3 2> <3 3 3 3>

<4 3 3 2> <3 3 3 3 3 3>

4와 2 사이에 3이 1개씩 증가하고, 이후에 3이 2개씩 증가한다.

체크포인트 값에 더해주면 된다.

 

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

def checkpoint(k):
    return int(((1/3)*(2*k+1/12))**0.5-5550/6666)

def checkpoint_idx(k):
    return int((1/2)*(3*k**2+5*k)+1)

def cvt_value(n):
    return int((1/2)*(3*n)*(3*n+5)+1)

for _ in range(int(input())):
    n = int(input())
    cp = checkpoint(n)
    idx = checkpoint_idx(cp)
    d = n-idx

    if d==0 : print(cvt_value(cp))
    elif 1<=d<=cp+1 : print(cvt_value(cp)+4+3*(d-1))
    else : print(cvt_value(cp)+3*d)

 

import sys
input = sys.stdin.readline

def solve(n):
    
    left = 1
    right = 2*10**9
    k = right
    
    while left <= right:
        mid = (left+right)//2
        y = mid*(3*mid+1)//2
        if y < n:
            left = mid+1
        else:
            right = mid-1
            k = min(k,mid)
    
    a = n-(k-1)*(3*k-2)//2
    
    if a <= k:
        h = 3*k - 2
        b = 3*a - 2
    elif a <= 2*k-1:
        h = 3*k-1
        b = 3*(a-k)
    else:
        h = 3*k
        b = 3*(a-2*k+1)-1

    answer = (h*(h-1)//2) + b
    return answer

for _ in range(int(input())):
    print(solve(int(input())))

• 근데 부동소수점 오류나서 그런거같은데 안풀려서 해설풀이로 풀었음
• 이분탐색 모듈 쓰는거도 익혀보기

코멘트

수학문제