[백준] 1449번 수리공 항승

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

1449번: 수리공 항승

 

테이프를 최소로 쓰기 위해선 어떻게 해야할까? 바로 구멍난 곳들을 왼쪽 기준으로 차례로 붙여나가면 된다.

---

SOLUTION CODE

# PYTHON

1) 좌표로 풀기

N,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
print(ans)

2) 좌표축소(구멍난곳만 좌표로 지정.입력값이 클때 사용)

import sys

num,tape = map(int,sys.stdin.readline().split())
holes = list(map(int,sys.stdin.readline().split()))
holes.sort() # [1,2,100,101]

N = 0
start = 0
for hole in holes:
    if start < hole: # 구멍이 테이프벗어남
        start = hole+tape-1 # 테이프붙인영역 갱신
        N+=1 # 테이프 한개더 필요
print(N)

---

# C++

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int N; // 물이 새는곳 개수
	int L; // 테이프길이
	bool coord[1001]={false};
    
	int start=0; // 테이프 시작
	int count=0; // 테이프 갯수
	
	cin >> N >> L;
	int HOLE;
	
	for(int i=0;i<N;i++){
		cin >> HOLE;
		coord[HOLE]=true;
	}
	
	while(start<1001){
		if(coord[start]){
			count+=1;
			start+=L;
		}
		else{
			start+=1;
		}
	}
	cout<<count;
}