[백준] 1449

문제 링크

풀이

그리디 알고리즘 문제입니다. 생각보다 오래 걸렸습니다. 처음에는 상태가 나쁜 파이프의 좌표(?)를 내림차순으로 정렬해서 뒤에서부터 고쳐나가는 것을 생각했는데요. 왜 그렇게 생각했는지 의아할 정도로 이로 인해 코드가 복잡해졌었습니다.

개인적인 생각으로는 다음의 코드도 정답에 가깝겠지만, 어디에선가 치명적인 실수를 하고 있는 듯 합니다. 관련하여 눈버깅을 해주실 분 있으시면 환경합니다.

• 실패 코드

n, l = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
arr.sort(reverse=True)

tmpl = l # 현재 테이프
loc = arr[0] # 현재 테이프를 붙이기 시작하는 위치
ans = 1 # 사용한 테이프의 갯수

for i in range(1, n) :
  # 현재 테이프를 사용하려고 시도한다.
  tmpl -= (loc - arr[i] + 1)

  # 만약 테이프를 다 쓰게된다면
  if(tmpl <= 0) :
    tmpl = l # 새로 테이프를 꺼내고
    ans += 1 # 사용한 테이프의 갯수 +=1
    loc = arr[i] # 현재 위치부터 다시 테이프를 붙인다.

print(ans)

앞 뒤 0.5 간격을 처음에는 고려하지 않았다가, tmpl -= (loc - arr[i] + 1)로 무마하려 한 부분에서 뭔가 경계값 에러가 발생한다고 추정합니다. 마지막으로 기억하는 것은 가령 인풋으로 4 2 1 2 3 100 이 들어오면, 분명 3을 출력해야 하는데 2를 출력했습니다.
단추부터 잘못 끼운 해당 코드를 지속하느냐? 아니면 그냥 오름차순으로 시작해서 머릿 속의 알고리즘을 그대로 받아적느냐 중 후자를 선택하여 해결했습니다.

• 정답 코드

n, l = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

tapeL = 0 # 이어지는 구멍들을 메우기 위해 지금까지 사용한 테이프의 길이
ans = 1 # 사용한 테이프의 갯수

for i in range(1,n) :
  recL = arr[i]-arr[i-1]
  tapeL += recL
  if(tapeL >= l) :
    ans += 1
    tapeL = 0
print(ans)

알고리즘

1. 현재 구멍과 그 다음 구멍의 간격을 받은 후(recL = arr[i]-arr[i-1]), 그 간격만큼 테이프를 붙이려 시도(tapeL += recL )합니다.
2. 불가능할 경우(tapeL >= 1, 즉 붙이려 시도했는데 정해진 테이프의 길이를 넘어서는 경우(tapeL>l)와 정확히 그 테이프를 다 쓴 경우(tapeL==l),
3. 테이프를 하나 더 꺼내고(ans+=1) 현재까지 사용한 테이프의 길이를 초기화(tapeL = 0)해줍니다.