백준 1117 색칠 1

2차원 그래프로 그려서 천천히 접근해볼까 했는데 W, H 가 최대 1억이 주어져서 그건 불가능 했다.
그러다 찾아낸 방법이 접는 모양이 가로 1번 세로 c 번 이기 때문데 각 좌표가 몇 번 중첩되어 있는지 알 수 있었고 이를 통해 간단히 계산으로 풀어낼 수 있었다.

📜 문제 바로 가기 : 색칠 1

제출코드

import sys
input = sys.stdin.readline

# 1억 x 1억이라 이차원 배열을 그리는건 무리라고 판단.
W, H, f, c, x1, y1, x2, y2 = map(int, input().split())

# 중첩되는 구간과 중첩되지 않는 구간이 생긴다.
# 중첩된 맨 오른쪽 좌표는 W-f, f 중 작은 좌표가 된다.
boundary = min(W-f, f)

if x1 <= boundary <= x2:
    k = 2 * (boundary-x1) + (x2-boundary)
elif boundary <= x1:
    k = (x2-x1)
else: # x2 <= boundary:
    k = 2 * (x2-x1)
    
# c+1 개가 겹치니깐 c+1 배가 된다.
print(W*H - k * (c+1) * (y2-y1))

---

접근방법

먼저 가로로 1번 접게 되면 boundary를 기준으로 중첩되는 부분과 중첩되지 않는 부분이 생긴다.
그 후에 세로로 c번 접게 되면 결국 모든 구간이 c번 겹치게 돼서 c+1 배가 된다.

그럼 이제 boundary 를 기준으로 왼쪽은 2*(c+1), 오른쪽은 c+1 이 됨을 알 수 있고
그냥 전체 면적 W x H에서 빼주면 끝이다.

x1에서 x2 까지 for 문으로 돌리는 방법을 먼저 시도해봤는데 x1=0, x2=1억 인 테스트 케이스가 있는지 시간초과가 나왔다.