BOJ 18187 평면분할 (python)

BOJ 18187 평면 분할

 

문제

무한한 크기의 이차원 평면에, 여러분은 최대 N개의 직선을 그릴 수 있다.

여러분은 기울기가 -1, 0, 1인 직선만 그릴 수 있다.

직선을 이용하여 평면을 최대 몇 개의 영역으로 분할할 수 있는지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 그릴 수 있는 직선의 개수의 최댓값을 의미하는 자연수 N이 주어진다.

 

출력

첫 번째 줄에 최대 몇 개의 영역으로 분할할 수 있는지 그 개수를 출력한다.

 

제한

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 100

 

풀이과정

 

규칙을 찾기 위해 기록을 해보았다

이때 규칙을 찾을 수 있었던 것이 증가개수가 짝수일 경우에는 다음회차에 바로 증가개수의 증가

홀수일 경우에는 한번더 같은 값으로 증가하고 증가개수의 증가가 일어난다는 규칙을 찾을 수 있었다.

N	증가개수	평면 개수
1	2	2
2	3	4
3	3	7
4	4	10
5	5	14
6	5	19
7	6	24
8	7	30

정확한 증명은 없었지만 해당 규칙을 코드에 적용시켜 보았다.

 

코드

N = int(input())
# 방문 검사를 위한 변수
visited = 0
# 처음에는 면이 1개이다.
temp = 1
# 결과값 초기화
result = 1
# N만큼 규칙에 따라서 더해질 것이다.
for _ in range(N):
    # 만약 값이 짝수라면 바로 temp에서 더해준다.
    if not temp % 2:
        # 바로
        temp += 1
    else:
        # 홀수인 경우에는 두번 더해지므로 이미 한번 더해졌다면
        if visited:
            # 더할 값 증가
            temp += 1
            # 방문검사 초기화
            visited = 0
        else:
            # 더해진 적이 없다면 방문 체크만 하자
            visited = 1
    # 결과값에 더할값을 더해주자
    result += temp

print(result)

확실한 증명이나 근거는 조금 부족해보였지만 일단 적용하니 그 규칙을 따른다는 것을 알 수 있었다.

아마 더 확실하거나 좋은 방법이 존재할 것 같다.