[C++] 백준 1449번 수리공 항승

1. 문제이해

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

1449번: 수리공 항승

 

물이 새는 곳의 개수(N)와 위치, 테이프의 길이(L)가 주어진다.

테이프를 이용해서 물이 새는 곳을 막으려고 할 때, 필요한 테이프의 개수를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

물이 새는 곳을 테이프로 막으려고 할 때, 필요한 테이프의 개수를 구하는 것이 목표이다.

 

예제 입력 1을 보자.

물이 새는 곳의 개수(N)는 4, 테이프의 길이(L)는 2

물이 새는 곳의 위치는 각각 1, 2, 100, 101 이다.

테이프의 길이가 2 이므로, 물이 새는 위치인 1, 2 를 1개의 테이프로 막을 수 있다.

그 다음 100, 101 을 1개의 테이프로 막을 수 있다.

이렇게 테이프로 물이 새는 위치를 막으려면 총 2개의 테이프가 필요하다.

 

위와 같이 테이프의 길이와 물이 새는 곳의 위치에 따라 필요한 테이프의 개수가 틀려진다.

여기서 고려해야 할 점은, 테이프를 최대로 붙일 수 있는 지점이다.

예제 입력 1에서, 테이프의 길이는 2이므로,

테이프를 붙이는 시작 위치인 1부터 시작해, 2, 100, 101 중 2까지만 붙일 수 있다.

처음으로 (테이프의 길이 <= 시작 지점부터 다른 누수 지점 까지의 거리) 가 되면,

해당 위치 전까지만 테이프를 붙일 수 있기 때문이다.

 

따라서, 예제 입력에서 처음으로 시작지점 ~ 누수지점 까지의 거리가 테이프의 길이를 넘어가는 지점은

(테이프의 길이(2) < 다른 누수지점(100) 과 시작 지점(1) 사이의 거리(99)) 이기 때문에,

해당 지점 이전인 2 까지만 테이프를 붙일 수 있게 된다.

따라서, 코드를 짤 때 적용해야 할 알고리즘은 다음과 같다.

 

1. 누수 지점을 오름차순 정렬 (누수 지점이 뒤죽박죽 입력되는 경우도 있기 때문)

 

2. (테이프의 길이 <= 시작 지점부터 다른 누수 지점(A) 까지의 거리) 가 되면,

필요한 테이프의 개수 + 1

테이프를 다시 붙이게 되는 시작 위치를 재설정

(새로운 시작 위치는 위의 다른 누수 지점(A)으로 한다.)

 

3. 2의 작업을 반복.

단, 마지막 테이프의 개수는 세어지지 않으므로 테이프의 개수 + 1 후 출력

 

 

 

3. 소스코드

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

int main() {
	int N;                // 물이 새는 곳의 개수
	int L;                // 테이프의 길이
	int location[1000];   // 물이 새는 곳의 위치
	int start;            // 각 테이프의 시작 위치
	int tape = 0;         // 필요한 테이프의 개수

	cin >> N >> L;

	for (int i = 0; i < N; i++) {
		cin >> location[i];
	}

	// 물이 새는 위치를 오름차순 정렬
	sort(location, location + N);

	// 시작 위치를 맨 처음 누수 위치로 설정
	start = location[0];

	for (int i = 1; i < N; i++) {
		// 테이프의 길이가 모자라게 되면
		if (L <= location[i] - start) {
			// 해당 지점 전까지 테이프를 사용했으므로 값 증가
			tape++;		
			// 테이프가 부족한 지점부터 시작위치 재설정
			start = location[i];
		}
	}
	
	// for문에서 마지막에 붙인 테이프는 세지 않았으므로 + 1
	cout << tape + 1;

	return 0;
}

2. 문제풀이에서 도출한 알고리즘을 이용한 소스코드는 위와 같다.

물이 새는 위치의 개수 위치, 테이프의 길이를 입력받는다.

 물이 새는 위치를 오름차순으로 정렬 후, 맨 처음 위치를 테이프를 붙이는 시작 위치로 정한다.

 

그리고, for문을 통해 (테이프의 길이 <= 시작 지점부터 다른 누수 지점(A) 까지의 거리) 가 되면,

필요한 테이프의 개수 + 1, 테이프를 다시 붙이게 되는 시작 위치를 재설정

한다.해당 과정을 반복 후, 필요한 테이프의 개수(tape + 1)를 출력한다.

 

 

---

어쩌다보니 그리디 알고리즘 풀이가 제일 많아 보이는 것 같은데..🤔

다른 유형 문제들도 많이 풀어 포스팅해보도록 해야지😤