18187 평면 분할

https://www.acmicpc.net/problem/18187

18187번: 평면 분할

---

 

접근

문제가 매우 짧아서 마음에 들었다. 기울기가 -1,0,1인 직선만 그릴 수 있다고 제한되어있어서 예시를 그리기 수월했다.

 

빈 공간을 직선이 가로지르면서 영역을 나누게 되지만, 직선을 교차했을 때도 영역이 나누어진다. 

직선을 그릴 때 빈 공간을 가르는 것보다 다른 직선 위를 지나갔을 때 더 많은 영역이 생기기 때문에 최대 개수를 구하기 위해서는 매번 다른 직선 위를 지나갈 선을 그려야 한다.

 

이 말은 매번 기울기가 다른 직선을 선택해야한다는 말이다. 기울기가 0인 직선으로 계속 나누려고 하면 2, 3, 4...개가 생기지만 기울기가 다른 직선을 고른다고 하면 2, 4, 7 ... 개가 생기기 때문이다. 그리다보면 아 기울기가 다른 직선을 골라야 더 많이 생기겠구나를 알게 된다.

 

그려진 직선 위를 다른 직선이 지나갈 때 몇 개의 영역이 생기는지 생각해보기로 했다.

 

기울기가 0인 직선을 그린 상태에서 기울기가 1인 직선을 그었다고 생각하자. 이 때 미리 그어진 직선 1개를 지나가면서 영역이 2개에서 4개로 바뀐다.

직선을 1개 만났기 때문에 그 직선 1개가 이루던 영역 2개를 쪼갰다고 볼 수 있다. 

 

만난 직선 개수와 관련이 있는 것 같아 직선 하나를 더 그려보았다.

 

아까 기울기가 다른 직선을 골라야 한다고 했으므로 기울기가 -1인 직선을 골라야 한다.

 

그림이 약간 난잡한데 어쨌든, 기울기가 -1인 직선을 그리면서 직선 2개를 만났다. 아까 직선 1개가 이루는 영역 2개를 쪼갰을 때 4개가 된 것처럼, 직선 2개가 이루는 영역 3개를 쪼개 6개로 만들었다.

 

여기까지 문제를 풀었을 때 (만난 직선의 개수 +  1) * 2가 답인줄 알았다. 이게 답 아닌가? 싶었는데 그림의 4번 영역은 쪼개지지 않았다. 

 

즉 만난 직선의 개수도 중요하지만 이전 영역을 전부 나누는 것은 아니라는 것이다. 여기서 살짝 막혔다. 

 

아까 구했던 공식인 (만난 직선의 개수 + 1) * 2는 (만난 직선의 개수 + 1)개의 영역을 직선이 지나가면서 쪼갠다는 말이다. 즉 만난 직선이 2개라면 직선 2개가 이루는 영역 3개를 직선이 지나가면서 쪼갤 때 3개가 더 생겨 총 6개가 된다는 말이다.

위 사진에서도 1, 2, 3번 영역을 지나가면서 5, 6, 7번 영역이 생겼다.

 

즉 이번 직선을 그림으로써 만난 직선의 개수 + 1개가 더 생긴다는 말이다. 이전 영역의 개수에 더해주면 된다.

 

만난 직선의 개수는 이미 그려진 직선들 중 이번에 그릴 직선의 기울기와 다른 직선의 개수를 구하면 된다. 나는 배열을 이용해 직접 개수를 다 누적시키고 덧셈뺄셈으로 계산했는데, 다른 사람들 보니까 더 깔끔하게 했더라.

 

i번째 영역의 개수 = i-1번째 영역의 개수 + 그렸던 직선들 중 이번에 그릴 직선의 기울기와 다른 직선의 개수

미흡했던 점

없었다!

---

#include <iostream>
int main() {
  int N, lines[3]{0}, areaCount = 1;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    areaCount += 1 + lines[0] + lines[1] + lines[2] - lines[i % 3]++;
  }
  printf("%d", areaCount);
}