[구현/수학] 백준 15700 타일 채우기 4 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

15700번: 타일 채우기 4

 

 

 

2. 문제 풀이

 N*M 크기의 벽에 2*1 또는 1*2 크기의 타일을 최대한 많이 배치하는 문제입니다.

 

 예를 들어, 4 * 3 크기의 벽은 아래와 같이 채울 수 있습니다.

 

 먼저 1 * 2 타일을 채우는 경우, (세로 길이 // 2) * 가로길이 = (3//2) * 4 = 4개를 배치할 수 있습니다.

 2 * 1 타일은 (세로 길이 % 2) * (가로 길이 // 2) = (3%2) * (4//2) = 2개를 배치할 수 있습니다.

 

 먼저 2 * 1 타일을 채우는 경우, (가로 길이 // 2) * 세로길이 = (4//2) * 3 = 6개를 배치할 수 있습니다.

 1 * 2 타일이 들어갈 자리는 없지만, 계산해보면 (가로 길이 % 2) * (세로 길이 // 2) = 0개입니다.

 

 

1*2 타일을 먼저 채우는 경우: (M//2)*N + (M%2)*(N//2)
2*1 타일을 먼저 채우는 경우: (N//2)*M + (N%2)*(M//2)

 두 경우를 정리하면 위와 같고, 둘 중 큰 경우를 출력합니다.

 

 

 

3. 코드

N, M = map(int, input().split())
res = max((M//2)*N + (M%2)*(N//2), (N//2)*M + (N%2)*(M//2))
print(res)