개요

[링크]백준 1449번: 수리공 항승

구멍위치와 테이프의 길이를 주고,
최소 테이프수를 이용해 구멍을 다 막는 문제

접근 방식

구멍의 반지름이 0.5이므로
구멍의 위치를 정렬한 후,
테이프를 붙인 마지막 위치를 저장하면
될 거 같다는 생각이 들었다.

마지막 위치를 맨 처음 구멍 위치로 두고,

마지막 위치+테이프 길이-1 (구멍 반지름이 0.5라서)
보다 큰 구멍 위치가 나올 때까지 벡터의 구멍위치를 다 무시하고,

큰 구멍 위치가 나왔다면 테이프갯수+1 및 마지막 구멍 위치를 갱신해주는 방식이다.

코드를 봐보자

코드

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

vector<int> holeLocation;

void input(int& holeAmount, int& tapeLength) {						//입력값 받는 함수
	int holes=0;													
	cin >> holeAmount >> tapeLength;
	for (int i = 0; i < holeAmount; i++) {
		cin >> holes;
		holeLocation.push_back(holes);
	}


}

void solution(int& holeAmount, int& tapeLength) {					//답 도출 함수
	sort(holeLocation.begin(),holeLocation.end());					//구멍위치 정렬
	int tapeEndPosition=holeLocation[0]+tapeLength-1, tapeCnt=1;	//tapeEndPoisition은 테이프가 끝나는 위치로 설정, 	
    																//이미 하나 붙인 셈이므로, tapeCnt=1
																	//구멍위치에서 테이프의 길이-1만큼 떨어진곳(한 구멍당 1의 길이이므로)
	for (int i : holeLocation) {									//각 구멍위치에서
		if (i > tapeEndPosition) {									//테이프의 마지막 위치보다 큰 구멍위치면
			tapeEndPosition = i+tapeLength-1;						//tapeEndPosition을 그 위치에서 테이프길이-1만큼 떨어진곳으로 갱신
			tapeCnt++;												//테이프 갯수++
		}
	}
	cout << tapeCnt;
}

int main() {
	int holeAmount = 0, tapeLength = 0;
	input(holeAmount,tapeLength);
	solution(holeAmount, tapeLength);
}

다른 방식

https://beginnerdeveloper-lit.tistory.com/117
에서 본 방식이다.

구멍위치를 정렬 후, 구멍위치와 마지막 구멍위치의 차이가
테이프 길이보다 클 경우, 테이프 수+1해주는 방식이다.

다만, 마지막 테이프는 갯수가 안 들어가므로 +1해준다.

코드

//다른 방식
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> locations;

int main() {
	int N = 0, L = 0,input=0,lastHole=0,tapes=0;	//구멍갯수,테이프길이,입력값받을 임시변수,마지막구멍위치,테이프갯수
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		cin >> input;
		locations.push_back(input);

	}
	sort(locations.begin(), locations.end());		//구멍위치 정렬
	lastHole = locations[0];						//마지막 구멍위치 정해주고
	
	for (int i = 1; i < N; i++) {					//각 구멍위치에서
		if (L <= locations[i] - lastHole) {			//테이프길이가 해당 구멍위치-마지막 구멍보다 크거나 같을 때
			lastHole = locations[i];				//마지막 구멍위치는 해당 구멍위치로 정해주고 
			tapes++;								//테이프 ++
		}
	}
	cout << tapes+1;								//마지막 테이프갯수는 세어지지 않으므로
													//출처 https://beginnerdeveloper-lit.tistory.com/117
}

문풀후생

정렬이 키포인트인 문제였다. 예제에서도 나오듯이 오름차순 정렬이 안 된 입력값도 들어와서