moner_ari   9달 전

[문제]

여러분은 골프를 좋아하는가? 나는 극혐. 골프가 너무 싫어서, 절대로 실수를 하지 않는 완벽한 골프 로봇을 만들기로 결심했다. 내가 골프공을 올려놓고 올바른 방향과 거리만 설정해둔다면, 내 로봇이 완벽하게 샷을 날려서 골프공이 한번에 홀에 들어갈 것이다. 그렇게 된다면, 골프라는 스포츠는 영원히 잊혀질 것이다.

불행히도, 내가 원하는 대로 로봇이 작동하지 않는다. 그래서 나는 지금 그린에서 첫 샷을 준비하고 있다. 사실 생각해보니 내가 만들어둔 거리 설정 손잡이에는 어떤 거리가 누락되어 있잖아? 그래도 아직 희망은 있다. 2번 이내의 샷으로 홀에 골프공을 넣으면 충분하다.

지금 내가 개발한 로봇이 주어졌을 때, 2번 이내의 샷으로 골프공을 넣을 수 있는 홀의 개수가 얼마나 될까?

--------

[입력]

입력의 첫 줄에는 설정할 수 있는 서로 다른 거리의 개수 N이 주어진다. 다음 N개 줄에는 손잡이의 i번 위치에 표시되어 있는 거리 설정을 나타내는 정수 ki가 주어진다.

그 다음 줄에는 현재 코스에 존재하는 홀의 개수 M이 주어진다. 다음 M개 줄에는 골프 봇과 j번 홀 사이의 거리 dj가 주어진다.

입력으로 주어지는 모든 수는 1 이상 200,000 이하 범위의 정수이다.

--------

[출력]

입력으로 주어진 골프 봇이 2번 이내의 샷으로 골프공을 넣을 수 있는 홀의 개수를 출력한다. 단, 골프 봇은 첫 샷에 홀보다 멀리 골프공을 날린 후 다음 샷에 반대 방향으로 공을 홀에 넣을 수 없다.

--------

[힌트]

(이해를 위해 일부 내용을 추가했습니다. 제가 임의로 넣은 부분은 이탤릭체로 나타냈습니다.)

[예제 1]에서 골프 봇은 1, 3, 5의 3가지 거리로 샷을 날릴 수 있으며, 현재 코스에는 거리가 2, 4, 5, 7, 8, 9인 6개의 홀이 있다. 이들 중 4개의 홀에 2번 이내의 샷으로 골프공을 넣을 수 있는데,

  • 1번째 홀(거리 2): 거리 1로 2번 연속으로 샷을 날리면 된다.
  • 2번째 홀(거리 4): 거리 3으로 샷을 날린 다음 거리 1로 샷을 날리거나, 그 반대 순서대로 진행하면 된다. 앞서 언급했듯 홀보다 멀리 골프공을 날려놓고 반대 방향으로 샷을 날리는 것은 불가능하다. 따라서 거리 5로 샷을 날린 다음 역방향으로 거리 1로 샷을 날릴 수는 없다.
  • 3번째 홀(거리 5): 거리 5로 샷을 날리면 단 1번의 샷으로 가능하다. 반드시 2번의 샷으로 골프공을 넣을 필요가 없다는 점에 유의하라.
  • 5번째 홀(거리 8): 거리 3, 5로 각각 샷을 날리면 된다. 마찬가지로 어느 거리를 먼저 날릴 것인지는 상관 없다.

4, 6번째 홀은 어떻게 거리를 설정한다고 해도 2번의 샷으로 골프공을 넣을 수 없다. 따라서 정답은 4이다.

댓글을 작성하려면 로그인해야 합니다.