글 읽기 - 1193번 시간초과에 대해 질문있습니다.

ywy000530 4년 전 0

분명히 답은 나오는데 시간초과가 나옵니다 ㅠㅠ 공지사항을 봐도 어느부분에 해당하는지 잘모르겠습니다. 어떤부분이 잘못되었는지 궁금해 이 질문을 올립니다.

N=int(input())
first_row=1
plus_row=1
room=1
if N==1:
    print('1/1')
while True:
    first_col=first_row
    plus_col=room+1
    room_col=1
    suc=0
    while True:
        first_col+=plus_col
        room_col+=1
        plus_col+=1
        if first_col==N:
            print('{0}/{1}'.format(room,room_col))
            suc+=1
            break
        elif first_col>N:
            break
    first_row+=plus_row
    plus_row+=1
    room+=1
    if suc==1:
        break

djm03178 4년 전 1

시간 초과가 전혀 어려운 게 아니고, 그냥 오래 걸렸으니까 시간 초과입니다. 10000000을 넣고 얼마 후에 답이 출력되는지 보세요.

dlgus2383 4년 전 1

이 문제는 일일이 계산해서 풀어도 가능하지만(시간 초과) 일정한 규칙을 가지고 있습니다.

1/1 홀

1/2 2/1 짝

3/1 2/2 1/3 홀

1/4 2/3 3/2 4/1 짝

홀에는 분모가 첫번째에서부터 1씩 증가하고

짝에서는 분자가 첫번째에서부터 1씩 증가하고 있습니다.

홀 짝 구하는 방법은

n = int(input())
count = 1
while n > count: // 홀 또는 짝 안에서 몇번째 숫자인지를 알려주는 루프입니다.
    n -= count   // n 은 결국 돌고 돌아 몇번째 숫자인지를 알려주고
    count += 1   // count는 몇째줄(홀짝)인지 알 수 있습니다.

몇번째 인지 아셨다면 count 를 이용해서 홀짝을 판별하시고

주어진 정보를 이용해서 출력만 하시면 됩니다.

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

문제

문제

출처

ICPC

1193번 시간초과에 대해 질문있습니다.

ywy000530 4년 전 0

djm03178 4년 전 1

dlgus2383 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말