글 읽기 - 반례를 알고싶습니다!

tkdrl2119 1년 전 0

위 문제를 푸는 도중에, 게시글에 있는 테스트케이스는 다적용해봤지만 아직도 반례를 찾진 못했습니다.

도와주실분 있으시다면 정말 감사드리겠습니다.ㅜㅜ

N,L = map(int,input().split())
leak=list(map(int,input().split()))

#0.5만큼의 간격 ? = 각 센치미터 단위의 중앙에 위치하여한다는 뜻
tape=1
dist=0#구멍간의 거리
for i in range(1,N):
    dist +=abs(leak[i]-leak[i-1]) 
    if L > dist:
        #0.5센티미터의 간격이기 때문에 같아서는 안된다. 같게되면
        #각 테이프의 끝자락에 물이셀것임
        
        continue
    else:
        tape+=1
        dist=0
print(tape)

tkdrl2119 1년 전 5

자아성찰을 통해 깨달았습니다.

저는 sort를 통해 해결했는데

sort를 안한다면 뒤죽박죽 들어온 물새는 구멍의 차를 테이프로 해결할 수 없다고 판단하더라구요

예를 들면

3 2

4 1 3

의 경우 사실 필요한 테이프는 2개이지만 (1따로, 4,3따로)

정렬을 안하면 4와1의차이 3, 1과 3의 차이 2 때문에 테이프가 3개필요하다 인지합니다.

도움이 되길 바랍니다 ^^!

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

문제

문제

출처

ICPC

반례를 알고싶습니다!

tkdrl2119 1년 전 0

tkdrl2119 1년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말