문제

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

• 그리디 문제

풀이

문제의 조건을 잘 읽다보면, 해당 문제가 그리디로 접근 가능한 문제임을 알 수 있다. 가장 왼쪽부터 시작하여 테이프를 붙이는 것이 최소의 테이프를 활용하는 방법이다.

space = [False] * 1001과 같이 모든 좌표를 담는 1차원 배열을 활용하여 문제를 풀 수도 있지만 만약 최대 좌표값이 1억 가까이 되는 큰 수가 나오게 된다면 적절한 풀이가 아니기 때문에 다음과 같이 구멍이 난 위치의 정수값들만을 활용하여 문제를 풀었다.

구멍이난 위치를 points 배열에 담아서 각 요소를 순회하면서 current_end 포인터를 움직이며 값을 비교하며 테이프를 붙여야하는 경우에는 cnt 변수에 값을 더하는 방식으로 최소 개수를 구했다.

N, L = map(int, input().split())
points = sorted(list(map(int, input().split())))
current_end = 0
cnt = 0
for p in points:
    if p > current_end:
        cnt += 1
        current_end = p + L - 1

print(cnt)

후기

첫번째 풀이에서 모든 좌표를 배열에 담아서 푸는 방식으로 접근했는데, 올바르게 풀어내지 못했다. 풀이를 참고하여 문제를 풀고나니 무척 단순한 문제였다.. 더 많이 공부해야할 것 같다.