백준1449번. 수리공 항승(파이썬)

백준 알고리즘 1449번 수리공 항승 문제입니다.

자세한 문제는 사진을 읽어보시기 바랍니다.

www.acmicpc.net/problem/1449

1449번: 수리공 항승

접근 방법

---

간단한 문제인데, 먼저 문제에서 중요한 부분은 물을 막을 때 좌우 0.5만큼 간격을 줘야 한다는 부분입니다.

이말은 즉 연속하는 물이 새는 부분은 그 길이의 합이 L+1이하이면 하나의 테이프로 다 막을수 있다는 뜻이죠.

이 정도 생각했으면 문제는 다 푼거나 마찬가지입니다.

N, L = input().split()
N = int(N)
L = int(L)
loc = list(map(int, input().split()))
loc.sort()
t_L = L
res = 0
for i in range(len(loc)):
    if i == len(loc)-1:
        res += 1
    else:
        t_L -= (loc[i + 1] - loc[i])
        if t_L < 1:
            res += 1
            t_L = L
        else:
            pass
print(res)

일단 N과 L을 입력받고, 물이 새는 부분을 list형태로 loc리스트에 저장해준 뒤 오름차순으로 정렬합니다.

그리고 임시로 사용할 t_L에 테이프 길이 L을 저장해주고 테이프 개수 res를 0으로 초기화시켜줍니다.

이제 for문을 사용해 loc리스트의 길이만큼 반복문을 수행시킵니다.

 

물이 새는 마지막 부분, 즉 loc의 마지막 요소일 때는 더 이상 추가로 물이 새는 곳이 없으니 테이프 개수를 한 개 증가시킵니다.

중요한 것은 그 외의 경우인데, 먼저 t_L에서 다음 물이 새는 장소와 현재 물이 새는 장소의 간격을 빼줍니다.

 

그리고 t_L이 1보다 작으면, 한 테이프로 다음 물이 새는 곳 까지 이어붙일 수 없으니

현재 물이 새는 곳만 막고 테이프 개수를 하나 증가시킨 뒤 t_L을 다시 L로 초기화시킵니다.

반면 t_L이 1이상이면 다음 물이 새는 부분을 하나의 테이프로 막을 수 있으니 pass하고 다음 반복으로 넘어갑니다.

 

예를 들어 물이 새는 곳이 1, 2, 3이고 테이프의 길이가 2라고 가정해봅시다.

맨 처음 i = 0일 때, t_L(2)에서 loc[i+1]=2 - loc[i]=1을 빼줍니다.

그러면 t_L은 1이 되는데, 이는 1이상이기 때문에 첫 번째와 두 번째 물이 새는 부분은 하나의 테이프로 막을 수 있습니다.

 

다음 반복으로 넘어가서 i = 1일 때, t_L(1)에서 loc[i+1]=3 - loc[i]=1을 빼줍니다.

그러면 t_L은 0이 되고, 이는 1보다 작기 때문에 두 번째와 세 번째 부분은 하나의 테이프로 막을 수 없습니다.

때문에 테이프 개수를 하나 추가시켜줍니다.

 

그리고 마지막 반복 i = 2일 때, if i == len(loc)-1부분에 의해 테이프 개수를 하나 증가시키고 반복문을 종료합니다.

이렇게 t_L의 값을 계속해서 차감해 그 값이 1이상인지, 1보다 작은지 검사하여 최종적으로 테이프의 개수를 구해냅니다.

 

이번 글은 이 정도로 마치도록 하겠습니다.

설명을 잘 못해서 이해가 되셧을지 걱정이네요.

감사합니다.