[백준] 1449번 수리공 항승 (c++)

[문제] https://www.acmicpc.net/problem/1449

1449번: 수리공 항승

 

---

[풀이]

✨주요 포인트

가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

   -> '정수'가 무슨 말인지 이해하기 조금 어려울 수 있다. 그냥 정확히 그 자리가 샌다고 생각해도 문제 없다.

 

테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

   -> 겹쳐서 붙인다는 말은 무슨 뜻인지 헷갈린다. 다만, 길이가 n인 테이프를 연결해 2n짜리로 보아도 된다는 뜻으로 해석하면 된다. 이음새도 완벽하게 커버쳐준다는 뜻.

 

그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다

   -> 예를 들어, 1과 2가 구멍이라면 길이 1(2-1)의 테이프를 사용하면 붙여도 된다고 생각할 수 있으니, 확실히 길이 2(2.5-0.5)의 테이프가 필요한 것이라고 명시해주는 것이다.

 

+입력의 경우에는 정렬된 상태로 들어온다고 하지 않았다. 정렬 작업이 필요하다.

 

 

✨알고리즘

1. 구멍의 개수, 테이프의 길이, 구멍의 위치를 각각 입력을 받는다.

2. 구멍의 개수에 따라 구멍의 위치를 저장할 배열을 동적할당한다.

3. 배열을 입력 받고, 정렬한다.

4. 배열을 0번째부터 훑으며, 두 구멍간 거리 + 1(좌우 0.5의 길이)가 tape의 길이보다 크다면, tape 하나가 커버할 수 있는 영역을 벗어났으니 tape의 개수를 증가시킨다.

5. tape의 개수를 출력한다.

 

---

 

(전체 코드)

#include <iostream>
#include <algorithm>

using namespace std;
int count_tape(int* count, int tape, int hole);

int main() {
	int hole, tape;
	int tapes;
	cin >> hole >> tape;

	int* count = new int[hole];
	for (int i = 0; i < hole; i++) {
		cin >> count[i];
	}
	sort(count, count + hole);

	tapes =  count_tape(count, tape, hole);

	cout << tapes << endl;
    
    delete[] count;

	return 0;
}

int count_tape(int* count, int tape, int hole) {
	int cnt = 0;
	int now;

	for (int i = 0; i < hole; i++) {
		now = count[i];
		while (true) {
			if (count[i+1] - now + 1 > tape)
				break;
			i++;
		}
		cnt++;
	}

	return cnt;
}

 

-배열의 동적 할당

int* count = new int[hole];

 배열을 고정 배열로 설정하면, 사용하지 않는 배열은 메모리의 낭비를 초래한다. 이 문제 같은 경우에는 결국 구멍이 1000개까지 있을 수 있으니(파이프가 맞나 리코더 아닌가), 배열을 1000까지 만들어야하는데 메모리가 낭비될 가능성이 매우 높다. 다행히 동적 배열로 간단하게 해결 가능한 문제이다.

 배열 버전의 new를 사용하면 동적으로 배열을 선언할 수 있다. new는 메모리를 할당받는 것이기 때문에 저장은 배열 포인터를 사용해 접근할 수 있는 길을 터두면 사용할 수 있다. 중괄호를 이용해 바로 초기화시켜줄 수도 있지만, 지금은 입력을 위한 배열이므로 그냥 선언만 했다.

 사용한 뒤에는 delete를 사용해 메모리를 해제하면 된다.