글 읽기 - 반례가 있다면 알려주시면 감사하겠습니다

20korea01 1년 전 0

주석으로 제가 어떤 생각으로 해당 문제를 접근하였는지 적었습니다.

해당 코드로 작성하였을 때 우선 시간초과는 뜨지 않았고 틀렸습니다 라는 결과가 나왔습니다. 혹시 코드를 읽어보시고 어디가 잘못되었는지 또는 반례가 있다면 알려주시면 감사하겠습니다.

from sys import stdin; input=stdin.readline
N, M = map(int, input().split())

# 리스트가 index 0부터 시작하므로 계산하기 편하게 앞에 0을 추가하여 A리스트가 index1부터 시작하도록 선언
A = [0] + list(map(int, input().split()))

s = sum(A)
for _ in range(M):
    idx, num = map(int, input().split())
    s = s - A[idx] + num # 매 회마다 sum함수를 사용할 경우 시간이 오래걸리므로 변경되는 idx의 정보만 사용
    A[idx] = num

    d, r = A[2]-A[1], A[2]//A[1]
    result0 = True if d >= 1 and int(d) == d else False # 공차가 양의 정수인지 확인
    result1 = True if r >= 1 and int(r) == r else False # 공비가 양의 실수인지 확인

    if result0:
        if s == int(N * (A[1] + A[-1]) / 2): # 등차수열의 합공식이 성립될 경우
            for i in range(3, N):
                # [1, 3, 2, 4]의 경우 등차수열 합 공식이 성립되지만 등차수열은 아님
                # 위와 같은 반례가 있으므로 합 공식이 성립되는 경우 등차수열인지를 판별
                if A[i] - A[i-1] != d: result0 = False; break
        else: result0 = False # 합 공식이 성립되지 않으면 등차수열이 아니므로 바로 False 반환
    
    if result1:
        try: # 공비가 1인 경우 0으로 나눌수 없는 ZeroDivisionError 발생
            if s == A[1]*(r**N - 1)/(r - 1):
                for i in range(3, N):
                    if A[i]//A[i-1] != r: result1 = False; break
            else: result1 = False
        except:
            # 공비가 1인경우 모든 수가 같기 때문에 num * N으로 등비수열인지 아닌지 판별
            if s != num * N: result1 = False

    if result0: print('+')
    elif result1: print('*')
    else: print('?')

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

문제

문제

출처

ICPC

반례가 있다면 알려주시면 감사하겠습니다

20korea01 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말