글 읽기 - 이분 탐색으로 해결할때 시간 초과 판정을 받습니다

(追記) (追記ここまで)

이분 탐색으로 해결할때 시간 초과 판정을 받습니다

22871번 - 징검다리 건너기 (large)

rodxx 4년 전 0

먼저 질문 봐주셔서 감사드립니다.

이분 탐색으로 풀고싶어서 최대한 코드를 짰는데 첫번째 코드는 시간초과 판정을 받고 두번째는 정답 판정을 받았습니다. 당연히 예제는 정상 출력됩니다.

첫번째 코드는 재귀함수로 코드를 짰다가 리커션 에러가 발생해서 DFS와 유사하게 스택을 이용한 반복문으로 작성했습니다. 첫번째 다리부터 출발해서 마지막 다리까지 도달할 수 있는지를 조건으로 설정했습니다.

두번째 코드는 조건 설정은 동일하지만 모든 다리를 다 검사하면서 첫번째 다리로부터 검사하는 다리까지 도달할 수 있는지 여부를 확인했습니다.

제가 봤을땐 두 방법 모두 시간복잡도가 O(N²log M) 으로 동일한거같은데 두 코드의 결과가 다른 이유가 궁금합니다. 도와주세요 ᅲᅲᅲ

그리고 이분탐색으로 푸는 방법중에 pypy말고 python3 로도 정답판정을 받는 코드가 존재할까요?? 부탁드립니다

import sys
input = sys.stdin.readline
n = int(input())
stone = [0] + list(map(int, input().split()))
s, e, r = 1, (n-1) * (1 + abs(stone[n] - stone[1])), 0
# 시간초과 판정받은 코드
while s <= e:
 m = (s+e) // 2
 flag = 0
 stack = [1]
 while stack:
 k = stack.pop()
 
 if k == n:
 flag = 1
 break
 
 for i in range(k+1, n+1):
 p = (i - k) * (1 + abs(stone[i] - stone[k]))
 if p <= m:
 stack.append(i)
 if flag:
 e = m-1
 r = m
 else:
 s = m+1
print(r)
# 정답판정받은 코드
while s <= e:
 m = (s+e) // 2
 d = [False] * (n+1)
 d[1] = True
 for i in range(2, n+1):
 for j in range(1, i):
 p = (i-j)*(1+abs(stone[i]-stone[j]))
 if d[j] and p <= m:
 d[i] = True
 break
 if d[n]:
 e = m-1
 r = m
 else:
 s = m+1
print(r)

rodxx 4년 전 0

생각해보니까 징검다리 방문 처리를 해주지 않아서 이미 방문한 징검다리가 또 스택에 들어가는 바람에 연산 시간이 오래 걸렸습니다.

아래 코드로 하니까 이중반복으로 구현했을때보다 짧은 시간에 해결 가능했습니다.

import sys
input = sys.stdin.readline
n = int(input())
stone = [0] + list(map(int, input().split()))
s, e, r = 1, (n-1) * (1 + abs(stone[n] - stone[1])), 0
while s <= e:
 m = (s + e) // 2
 flag = 0
 stack = [1]
 v = [False]*(n+1)
 v[1] = True
 while stack:
 k = stack.pop()
 if k == n:
 flag = 1
 break
 for i in range(k + 1, n + 1):
 p = (i - k) * (1 + abs(stone[i] - stone[k]))
 if p <= m and not v[i]:
 stack.append(i)
 v[i] = True
 if flag:
 e = m - 1
 r = m
 else:
 s = m + 1
print(r)

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)