[백준18187번][백준][baekjoon][18187번][평면분할][Python][파이썬]

문제링크

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

18187번: 평면 분할

 

문제

 

풀이

좋아하는 TV 프로그램인 문제적남자에서 비슷한 문제를 본 적이 있는 것 같네요. 차이가 있다면 기울기가 -1, 0, 1인 직선만 그릴 수 있는 조건이 있습니다. 일단 저는 그리디로 접근했다가 DP로 풀이했습니다.

 

직선 개수를 늘려가면서 규칙을 찾았습니다.

 

직선 개수	분할된 면의 수	증가하는 개수	직선이 만나는 점의 수
1	2	+2	0
2	4	+2	1
3	7	+3	2
4	10	+3	2
5	14	+4	3
6	19	+5	4
7	24	+5	4
8	30	+6	5
9	37	+7	6

 

실제 풀이할땐 테스트 케이스를 5에서 6 정도까지만 써보면서 규칙을 찾았지만, 위에 표에서 보인 바와 같이 9 정도 써보면 대충 규칙이 보이네요. 주어진 직선의 종류는 세 가지(기울기 -1, 0, 1)입니다. 처음, 직선의 개수가 3개 이하 일땐 종류가 겹치는 직선이 없어서 규칙이 없지만, 그 이후부터는 일정한 규칙을 보입니다. 분할이 되려면 두 개의 직선이 한 점에서 만나는 경우이며, 직선의 종류가 3개이기 때문에 3의 배수가 넘어갈 때마다 직선이 만나는 점의 개수가 증가하지 않는 것을 볼 수 있습니다. 

 

즉 직선이 늘어날 때마다 분할된 면이 증가하는 개수가 늘어나는데, 증가하는 개수가  3의 배수+1 일때만 늘어나지 않습니다. 여기까지는 그리디이지만 이전의 평면 개수에서 증가하는 면의 수를 누적해서 계산해야 하므로 DP를 이용해 봤습니다. 이를 코드로 옮기면 아래와 같습니다.

 

코드

#Python

testcase=int(input())
 
dp=[ 0 for _ in range(101) ]
 
dp[1]=2
dp[2]=4
 
plusnum=3
 
for i in range(3, testcase+1):
    dp[i]=dp[i-1]+plusnum
    if i%3!=0:
        plusnum+=1
 
print(dp[testcase])
        
 

 

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.

 

감사합니다.