글 읽기 - (python) 왜 틀렸는지 도저히 모르겠습니다.

chaos7061 5년 전 0

우선 감사하다는 말씀부터 드리겠습니다. 그리고 코드가 지저분해서 죄송합니다.

주석은 성심성의껏 달아놓았습니다.

예제코드와 질문글에 있는 반례코드 모두 정상작동 하고, 어느 부분이 틀렸는지 도저히 제 눈에는 보이지 않아서 이렇게 질문 글을 남깁니다.

고수님들의 조언 기다리겠습니다! 감사합니다~

---------수정된 코드를 댓글에 첨부했습니다-----------

sait2000 5년 전 1

21~28이 매우 오래 걸릴 수 있습니다

첫 줄에 -1 10^18 같은 게 들어오면 저 루프는 대략 10^9번 실행됩니다

chaos7061 5년 전 0

좋은 지적 감사합니다. 혹시 저런 방법을 쓰지 않고 찾아 낼 수 있는 방법이 있을까요?

chaos7061 5년 전 0

우선 약수를 이용해서 기존에 오류가 있던 부분만 수정해봤는데(시간 복잡도는 고려하지 않음) 여전히 틀렸습니다가 나옵니다. 어느 부분이 문제일까요 ㅠㅠ?

import sys

# 약수 구하기
def yaksu(m, t):
    idx = 1
    while idx ** 2 < t + 1:
        if t % idx == 0:
            if idx ** 2 == t:
                m.append(idx)
            else:
                m.append(idx)
                m.append(t
        idx += 1
    return m

# 유효성 검사
def validate(m, a, b, now):
    new = []
    for i in m:
        # m의 원소 중 하나인 i씩 충전을 해서 잔고가 now에서 b가 되는게 적합한지 판독.
        tmp = a + now
        tmp += i * (abs(tmp)
        if tmp < 0:
            tmp += i
        if tmp == b:
            new.append(i)
    return new



n = int(sys.stdin.readline())
# m의 후보가 될 수 있는 집합 생성
m = []
# 현재 잔액 변수
now = 0
# 충전이 이루어지는지 확인하기 위한 변수
chk = False
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    # 출금인 경우
    if a < 0:
        # 충전이 이루어질때,
        if now < (-1)*a:
            # 변수 on
            chk = True
            # 총 충전된 금액 t
            t = b - now - a
            # m이 비어있다면,
            if not m:
                # t의 약수들을 m에 넣고, 현재 로그 a, b와 now값을 이용해 유효성 검사.
                m = yaksu(m, t)
                m = validate(m, a, b, now)
            # m이 존재한다면,
            else:
                # 마찬가지로 총 충전된 금액
                t = b - now - a
                # 새로운 t에 대해서도 여러 약수가 존재하므로 기존의 m과 교집합을 구해야함. 그 후 유효성 검사.
                tmp = []
                tmp = yaksu(tmp, t)
                m = list(set(m).intersection(set(tmp)))
                m = validate(m, a, b, now)
        else:
            # 충전 되지 않은 출금의 경우, m이 존재할때만 유효성 검사를 하고 넘어간다.
            if m:
                m = validate(m, a, b, now)
        # 출금인 경우 무조건 now = b가 된다.
        now = b
    # 입금
    else:
        now += a

# 충전이 한 번도 이루어지지 않았다면 임의의 양수 M일 것.(1을 출력하도록 함)
if not chk:
    print(1)
# 충전이 이루어졌을때, m이 존재하면 m 원소중 9 * 10**18 보다 작은 수 중 하나를 출력.
else:
    if m:
        for i in m:
            if i <= 9 * 10**18:
                print(i)
                break
    # 존재하지 않으면, 로그에 문제가 있는 것이므로 -1 출력.
    else:
        print(-1)

chaos7061 5년 전 0

추가 발견) 맨 아래 77~81번 줄 출력 부분에서 만약 list m은 존재하지만 유효한 범위 내의 수를 갖지 않는 경우, -1을 출력할 수 있도록 예외 처리 하였음에도 틀렸습니다가 뜹니다 ㅠㅠ

chaos7061 5년 전 0

또 추가발견) 63~65번 줄 부분은 validate 함수와 맞지 않는 내용이어서 그냥 now + a != b일때 chk = True로 하고 break 걸었더니 드디어 시간초과가 뜨네요!

시간초과가 뜨고 행복한건 처음이네요 ㅠㅠ.. 아마 약수를 찾는 과정에서 범위를 좀 더 효율적으로 설정해줄 필요가 있는 것 같아요.

지금까지 총 얻어낸 반례로는 아래 같은 것들이 있네요.

이 쉬운 예외들을 간과하고 있었네요...

input 1
1
100 300

output 1
-1

input 2
2
1000 1000
-500 300

output 2
-1

input 3
2
4000 4000
-5000 1000

output 3
2000

sait2000 4년 전 1

좀 큰 힌트같기는 한데, 모든 약수를 다 구할 필요 없습니다. 최대공약수를 구하는 빠른 알고리즘(유클리드 호제법)으로 최대공약수만 계산하면 됩니다. 그리고 유효성 검사도, 그냥 b보다 크기만 하면 통과한다는 걸 생각해보면 알 수 있습니다.

chaos7061 4년 전 0

힌트 정말 감사합니다!!!

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

문제

문제

출처

ICPC

(python) 왜 틀렸는지 도저히 모르겠습니다.

chaos7061 5년 전 0

sait2000 5년 전 1

chaos7061 5년 전 0

chaos7061 5년 전 0

chaos7061 5년 전 0

chaos7061 5년 전 0

sait2000 4년 전 1

chaos7061 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말