글 읽기 - 최악의 코드로 가는 중입니다. 공배수 공약수 말고 룰 정해서 해결할 수 있을까요

ele7004 4년 전 0

안녕하세요.

이것만 거의 몇시간째 파는 중인데,

공배수 공약수를 안쓰고 큰 쪽을 고정시키고 작은 것을 계속 더해서 뺑뺑이돌려서

해당되는 수 조합을 캐치하려고 했는데 생각보다 너무 안되네요.

FAQ에 올려주신 분 예제로 해보니 반례가

10 12 2 12 - 최대값이 같을 때

12 10 12 10 - 최대 최소 값이 같을 때

이 부분에서 오답이 발생합니다.

40000 39999 40000 39999 요 값에서도 어떻게 보면 틀렸어야 하는데 공배수가 없나봐요.. 허허

저 위에 안되는 두가지를 지금 예외처리 하려고 했더니, 이렇게 조건마다 하나씩 필터링 하는 것 같아

최악의 코드로 가고있다고 생각합니다. (논리력보단 그저 브루트포스같이..)

혹시 고수님들 조언 주실 수 있을까요 ㅠㅠ

부탁드립니다.

import sys

n = int(sys.stdin.readline().rstrip())
result=[]
for i in range(n):
    args = sys.stdin.readline().rstrip()
    args = args.split(' ')
    m = int(args[0])
    n = int(args[1])
    x1=int(args[2])
    y1=int(args[3])
    std = 0
    max = 0
    min = 0
    ans=0
    total=0
    big=0

    if(m>n):
        max = m
        min = n
        std = y1
        big = x1
    else:
        max = n
        min = m
        std = x1
        big = y1

    total = std
    if(m<x1 or n<y1):       #유효성검사
        result.append(-1)
        break

    if(m == 1 or n == 1):       #1 1 일때
        if(m == 1 and n == 1):
            result.append(1)
            continue
        else:
            result.append(max-big)      #하나는 1 이면서 하나는 다른숫자
            continue

    if(big%std == 0 and m==x1 and n == y1):     #하나의 숫자가 다른 하나의 약수
        result.append(big)
        continue
    elif(m==x1 and n==y1):
        result.append(m*n)
        continue

    while(total <= m*n):                #반복하여 찾아내는 코드

        if(total % max == big):
            result.append(total)
            ans=1
            break
        total += min

    if(ans == 0):
        result.append(-1)

for i in result:
    print(i)

nahwasa 4년 전 0

음.. 힌트는 둘중 하나만 생각해보세요!

10 12 3 9

라면 어차피 둘다 맞아야하니 3에 대해선 초기설정만 잡고, 이후로는 9만 생각하는거죠!

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

문제

문제

출처

ICPC

최악의 코드로 가는 중입니다. 공배수 공약수 말고 룰 정해서 해결할 수 있을까요

ele7004 4년 전 0

nahwasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말