1477 : 청개구리
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 18 회
- 시도횟수
- 111 회
문제
한국에서는 청개구리들의 말썽이 가히 믿기 어려울 정도이다.
그도 그럴 것이, 청개구리들은 여러분이 돌보고 있는 논 위를 밤사이에 마구 뛰어 다니면서 벼들을 쓰러뜨리기 때문이다
(이로 인해 농부 창호의 논도 많은 피해를 입었다고 한다).
아침이 되어, 쓰러진 벼들을 파악한 당신은 가장 큰 해를 끼친 청개구리가 남긴 발자취를 파악하고 싶어 한다.
청개구리는 논을 언제나 일직선으로 쭉 뛰어가며, 한 번에 뛰는 간격도 언제나 같다.
논은, 그림 1처럼 모눈의 교점들에 벼가 심어져 있는 구조를 하고 있다.
그리고 문제의 청개구리들은 논 밖에서 논으로 들어와, 일직선으로 팔짝팔짝 뛰어 정확하게 벼만 짓밟고 반대편 논 밖으로 나간다.
그림 2를 참고하라.
그림 3처럼, 여러 청개구리들이 제각기 다른 방향에서부터 논으로 들어와 서로 다른 방향으로 뛰어갈 수 있다.
그리고 개구리에게 밟힌 벼는 쓰러진다. 여러 개구리에게 여러 번 밟히는 벼도 있다.
하지만, 개구리들이 지나간다고 자신의 경로가 그림 3처럼 직선으로 남는 것은 아니다.
우리가 아침이 되어 확인할 수 있는 것은 그림 4처럼, 쓰러진 벼들 뿐이다.
그림 4를 보면, 개구리들이 몇 마리가 와서 어느 방향으로 어느 간격으로 벼를 밟고 갔는지 그 경로를 재현할 수 있다.
단, 벼를 세 포기 이상 밟은 개구리의 경로만 생각하기로 한다.
그리고 이것을 개구리 경로라고 편의상 일컫겠다.
그렇다면, 그림 4의 상황이라면 그림 3과 같은 세 개의 개구리 경로가 있다고 말할 수 있다. (물론 다른 가짓수도 있을 수 있다.)
한편, 첫째 칸에서 수직으로 내려가는 경로는 간격이 4인 개구리 경로일 수도 있지만,
이 경로의 영향을 받은 벼는 두 포기밖에 없기 때문에 고려하지 않는다.
그리고 둘째 줄 셋째 칸(2, 3), 셋째 줄 넷째 칸(3, 4), 여섯째 줄 일곱째(6, 7) 칸을 지나는 경로는 일직선이고 벼가 세 포기가 속해 있지만,
간격이 일정하지 않기 때문에 개구리 경로로 인정하지 않는다.
어떤 개구리 경로에 속하는 선에는, 다른 개구리 경로에 속하는 벼가 있을 수 있다.
예를 들어 위 그림에서 (2, 1), (2, 3), (2, 5), (2, 7)은 개구리 경로인데, 이 선 안에는 (2, 6)처럼 다른 개구리에게 밟힌 벼가 또 있다.
그리고 사실은, 쓰러진 벼 중에는 어느 개구리 경로에도 속하지 않은 벼도 있을 수 있다. 개구리에게 밟힌 벼라고 해서,
모두 다 조건을 만족하는 '개구리 경로'에 속하는 것이 아니기 때문이다.
이번 문제는, 가능한 개구리 경로를 모두 조사하여, 벼를 가장 많이 밟았다고 결론지을 수 있는 개구리 경로를 찾아,
그 경로가 지나게 되는 벼 포기의 수를 출력하는 것이다. 그림 4의 경우, 정답은 7이다.
여섯째 줄부터 가로로 벼 일곱 포기를 모두 밟는 경로가 있기 때문이다.
입력형식
출력형식
입력 예6 7 14 2 1 6 6 4 2 2 5 2 6 2 7 3 4 6 1 6 2 2 3 6 3 6 4 6 5 6 7 |
출력 예7 |