문제링크

크기가 1001 짜리 좌표 리스트 입력 및 리스트를 False로 만들기

N, L = map(int, input().split())
coord = [False] * 1001

구멍이 난 값만 True

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

coord[x] 가 True 인지 판단

answer = 0
x = 0
while x < 1001:
    # coord[x] 가 True 인지 판단
    if coord[x]:
        # 테이프 쓸 경우 answer 에 1추가
        answer += 1
        # 테이프 를 쓸 경우 x 좌표도 L 길이 만큼 점프
        x += L
    else:
        # 구멍이 안난 경우 그냥 1 늘리기
        x += 1
print(answer)

예제 입력 1:

예제 입력 2:

예제 입력 3:

예제 입력 4:

구멍이 하나이고 테이프 길이가 1이고 테이프 하나만 사용

예제 입력 5:

구멍이 5개이고 테이프 길이가 1이고 테이프 5개만 사용

예제 입력 6:

구멍이 1개이고 테이프 길이가 1000일경우 테이프 1개만 사용

예제 입력 7:

구멍이 2개이고 테이프 길이가 1000 경우 테이프 1개 사용

구명이 2개이고 테이프 길이가 999일 경우 테이프를 2개를 쓸수 밖에 없음

전체 코드

N, L = map(int, input().split())
# 크기 1001 짜리 좌표 리스트 False 로 만들기
coord = [False] * 1001

for i in map(int, input().split()):
    # 구멍이 난 값만 True
    coord[i] = True

answer = 0
x = 0
while x < 1001:
    # coord[x] 가 True 인지 판단
    if coord[x]:
        # 테이프 쓸 경우 answer 에 1추가
        answer += 1
        # 테이프 를 쓸 경우 x 좌표도 L 길이 만큼 점프
        x += L
    else:
        # 구멍이 안난 경우 그냥 1 늘리기
        x += 1

print(answer)

좌표압축

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

정리

1. 무식하게 모든 경우의 수를 다 살펴봐도 시간초과 나지 않을지 확인
2. 될거 같으면 완전 탐색으로 푼다

• 안될꺼 같으면 더 효율적인 방법으로 알고리즘을 찾아본다. (그리디, dp, 이분법 등...)

3. 그리디는 반례가 없을까 신중하게 고려해야 한다.