백준 그리디 문제풀이 입니다.

문제

https://www.acmicpc.net/problem/1449

[나의 풀이]

N, M = map(int, input().split(" "))

holes = list(map(int, input().split(" ")))
holes.sort()

# print(holes)

ans = 1
loc = holes[0]

for i in range(1, N):
    print("인덱스 : ", i)
    print("현재 위치 : ", loc, " 다음 위치 : ", holes[i])
    if holes[i] < loc + M:
        continue
    print("테이프 추가")
    ans += 1
    loc = holes[i]

print(ans)

그리디 문제입니다. 문제에서 보듯 현재 위치에서 막아야 하는 다음 파이프 위치까지의 거리를 파악하여 총 필요한 테이프 갯수를 구하는 문제입니다. 테이프를 붙히기 시작한 위치에서 테이프 길이만큼 커버되는 지점까지 1개의 테이프를 붙히고 그 이상 범위를 초과할 때 테이프를 추가하는 방식으로 해결하였습니다.🐹🐹🐹

[다른 사람의 풀이]

K, L = map(int, input().split())

coord = [False] * 1001
for i in map(int, input().split()):
  coord[i] = True

ans = 0   
x = 0
while x < 1001:
  if coord[x]:
    ans += 1
    x += L
  else:
    x += 1 

저의 풀이 이외에 위와 같이 최대 파이프 길이의 Boolean 리스트를 만들고 물이 새는 파이프 위치에 True 값을 입력해주고, 해당하는 위치가 True이면 테이프 1개 추가 후 바로 테이프 길이만큼 더한 값의 위치로 이동하여 해결하는 방식을 볼 수 있었습니다. 위 풀이는 물이 새는 모든 파이프 지점을 반드시 확인하지 않아도 된다는 장점이 있었습니다.🐤🐤🐤

감사합니다.