글 읽기 - 차이를 모르겠습니다.

dpf226 2년 전 0

근의 공식을 이용해서 풀었는데요.

ax²+ bx + c = 0

x² - nx - (n-k+1) = 0 이렇게 나와서 a = 1, b = -n, c = -(n-k+1) 두고 했습니다.

x = n +- (n² + 4(n-k+1))^0.5

6줄 조건에서 루트 안에 들어가도 정수로 나올 수 있는지 검사하고자 조건을 달았는데 아래와 같이 적지 않으면 틀린 것으로 됩니다.

주석으로 표시할 것처럼 조건을 달면 틀리더군요.. 답안의 조건이 제곱을 해줌으로써 다시 원상복귀했을 뿐 주석으로 표시한 루트 씌워서 비교하는 것과 다를 바가 없지 않나요? 왜 틀리는 건지 모르겠습니다..

다음 코드 또한 궁금한 점이 있는데요. 이 코드는 아예 예외 처리를 이용해서 짰습니다. 근의 공식을 이용한 뒤 루트 안에 음수가 들어가서 에러가 나거나 정수로 형변환할 때 에러가 나는 등 그러한 오류가 발생할 경우 해가 0 이상의 정수로 나올 것이라 생각되지 않았고 no를 출력하도록 했습니다. 왜 두 번째 코드가 틀린 지 그 반례를 모르겠습니다..

첫 번째 질문과 두 번째 질문에 대한 반례를 아시는 분이 계시다면 조언 부탁 드립니다...

def solve():
    sq = n**2 + 4*(n-k+1)
    if sq < 0:
        print("NO")
        return
    if sq != int(sq**0.5)**2:               # if sq**0.5 != int(sq**0.5): 이렇게 하면 틀림
        print("NO")
        return
    
    sol1, sol2 = (n + (sq**0.5))/2, (n - (sq**0.5))/2
    if sol1 != int(sol1) or sol2 != int(sol2):
        print("NO")
        return
    
    if sol1 >= 0 and sol2 >= 0:
        print("YES")
        return

n, k = tuple(map(int, input().split()))
solve()
            
##########################################################################


n, k = tuple(map(int, input().split()))

try:
    x = (n + (n*n + 4*(n-k+1))**0.5)/2
    y = (n - (n*n + 4*(n-k+1))**0.5)/2
    if (x == int(x) and y == int(y)) and (x >= 0 and y >= 0):
        print("YES")
    else:
        print("NO")

except:
    print("NO")

x**0.5는 결과를 float으로 계산합니다. float이 가지는 정밀도는 53비트(약 8*1e15) 정도로, 15자리를 넘는 수는 정확하게 계산하지 못합니다. 문제는 2^64에 가까운 수들을 다루고 있기 때문에 **0.5로 제곱근을 취할 경우 틀린 결과를 내놓을 수 있습니다. 맞으신 코드 역시 맞도록 정해진 것인지 우연히 맞는 데이터만 있는지 알기 어렵습니다.

wider93 2년 전 1

참고로 python을 사용하신다면 n>= m**2인 최대의 정수 m을 반환하는 함수 math.isqrt가 이미 구현되어 있으니, 그 쪽을 사용하시는 게 좋습니다.

dpf226 2년 전 0

조언 감사합니다! 저도.. 정확하게 계산이 안되다 보니 틀린 결과를 내놓을 수 있을 것 같다 란 생각이 들더군요.. 그런데 그 원인을 몰랐는데 덕분에 추측할 수 있게 되었습니다.

넵 **0.5 방법 말고 math 라이브러리 쓰는 방법도 있는데 제가 코드에서는 저렇게 짰네요^^;; 댓글 달아주셔서 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

차이를 모르겠습니다.

dpf226 2년 전 0

wider93 2년 전 1

wider93 2년 전 1

dpf226 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말