흙길 보수하기( BOJ 1911 )

문제

흙길 보수하기 : https://www.acmicpc.net/problem/1911

1911번: 흙길 보수하기

 

문제 파악하기

• 물웅덩이가 입력되는데 시작값과 끝값이 입력됩니다. 여기서 말하는 값은 좌표와 좌표 사이의 번호를 의미합니다.
  예를 들어 1은 (0 ~ 1) 사이를, 6은 (5 ~ 6) 사이를 의미합니다.
• 물웅덩이는 널빤지로 덮을 수 있으며 널빤지의 개수를 최소로 해서 모든 물웅덩이를 덮어야 합니다.
• 그렇다면 널빤지를 단순히 물웅덩이의 시작 지점부터 덮으면 될까요??? 정답은 그렇다 입니다.

 

문제 해결하기

• 널빤지를 물웅덩이의 시작점부터 덮지 않는 방법이 있다고 생각해봅시다, 시작점부터 덮지 않는다면 2가지 방법이 있습니다.
• 우선 시작점 이후부터 덮어봅시다. 그럼 항상 널빤지는 1개가 추가로 필요하기 때문에 최솟값을 구할 수 없습니다.
• 그럼 시작점 이전부터 덮어봅시다. 하지만 이 방법은 시작점부터 널빤지를 덮는 방법에 항상 포함되게 됩니다.
• 따라서 물웅덩이가 시작점부터 널빤지를 덮어가면 최소의 값을 찾을 수 있게됩니다.

 

후기

처음 입력에 대한 설명이 미흡해서 머리 아팠던 문제입니다. 전형적인 그리디 방식의 문제풀이라서 그리디를 처음 배우는 사람들에게 소개시켜주기 좋아보입니다.