[BOJ #1449] 수리공 항승

BOJ #1449, 수리공 항승 문제입니다.

 

간단하게 그리디 알고리즘을 이용하는 문제입니다. 테이프의 길이와, 파이프에서 물이 새는 위치가 주어지면 물이 새는 모든 위치를 막으려면 최소 몇 개의 테이프를 이용해야 하는지를 출력하는 문제입니다. 단, 테이프는 자를 수 없으며 무한 개 가진 것으로 간주합니다. 추가적으로 물이 새는 지점의 좌우로 0.5cm까지 테이핑해야 물을 막은 것으로 간주합니다. 따라서 가령 1과 3에서 물이 새고 있고 이것을 하나의 테이프로 막고자 하면 1의 왼쪽 0.5, 사이 거리 3 - 1 == 2, 3의 오른쪽 0.5로 길이 3 이상의 테이프가 필요한 것이죠. 즉 길이 n의 테이프로는 최대 간격이 n - 1인 구멍까지만 막을 수 있습니다.

 

그리고 이 문제 한참 헤맸던 것이... testcase에서 물이 새는 위치를 입력할 때 정렬된 채로 입력되지 않습니다! 문제엔 아무런 언급도 없고 예제는 정렬되어서 들어와서 몰랐네요. 그리디 알고리즘을 사용하는 문제가 아닌 것인지 의심이 들어서 수많은 예시를 만들어 테스트해 보고 결국 정렬을 하는 것으로 문제를 해결했습니다.

 

제 코드의 핵심부분입니다.

int stop = 0;
int cnt = 0;
while (stop != N) {
	stop += stopCnt(out, stop, N, L);
	cnt++;
}
printf("%d", cnt);

이 코드를 보면 이해가 어렵고, stopCnt 함수의 원형을 봐야 합니다.

int stopCnt(int* out, int start, int N, int L) {
	int cnt = 0;
	int end = out[start] + L - 1;
	while (out[start] <= end && start < N) {
		start++;
		cnt++;
	}
	return cnt;
}

먼저 out은 물이 새는 위치를 담은 배열입니다. 입력 이후 정렬해둔 상태입니다. start는 테이프의 맨 왼쪽 끝으로 막을 위치의 '인덱스'입니다. 즉 out[start]가 테이프의 왼쪽 끝으로 막을 위치인 것이죠. 그리고 end는 out[start]에서 테이핑을 시작했을 때 어떤 '위치'까지 막을 수 있는지를 계산한 것입니다. 글의 서두에서 이야기한 내용을 반영해 end는 out[start] + L - 1로 초기화합니다. 이후 out[start]부터 end 사이에 몇 개의 물 새는 위치가 있는지를 세고(cnt) 그것을 반환합니다.

 

그러면 이제 main 코드를 이해할 수 있습니다. while문 내 한 번의 시행에 대해 설명드리자면, stop이 0에서 시작해 처음에는 stopCnt(out, 0, N, L)이 더해집니다. 이 함숫값은 새는 위치 '인덱스' 0번째 값부터 시작해서 길이 L의 테이프로 막을 수 있는 위치의 수를 나타내죠. 이것을 예를 들어 a라고 하면 stop의 값은 a가 될 것입니다. 그런데 배열의 인덱스는 0부터 시작하므로 현재 파이프에는 a - 1번째 위치까지가 막힌 상태일 것이고 다음부터 우리는 a번째 위치부터 탐색을 하면 됩니다. 따라서 stopCnt의 값을 그대로 더할 수 있는 것입니다. 그리고 이 작업을 stop == N이 될 때까지(모든 위치를 막을 때까지) 반복합니다.

 

이 문제에 그리디 알고리즘을 적용할 수 있는 이유는 무엇일까요? 그리디 알고리즘을 적용하기 위해서는 '이보 전진을 위한 일보 후퇴'하는 선택을 할 필요가 없어야 합니다. 저는 이 문제를 남은 위치들 중 가장 왼쪽의 위치에 테이프의 가장 왼쪽을 붙여나가는 방식으로 풀었습니다. 저는 이 판단을 다음 두 가지 사고과정을 통해 했습니다.

1. 가장 왼쪽의 위치에 테이프를 붙이고자 할 때는 테이프의 가장 왼쪽을 붙이는 것이 가장 효율적이다.
2. 가장 왼쪽의 위치에 테이프를 붙이지 않는다면 어차피 나중에 가장 왼쪽 위치를 막기 위해 테이프를 붙여야 한다. → 그럴 바엔 가장 왼쪽부터 시작한다.

그리디 알고리즘을 연습할 수 있는 좋은 문제였으나, 입력이 정렬되어 주어지지 않는다는 것이 언급되어 있지 않아 살짝 아쉬웠던 문제였습니다.