파이썬) ZOAC 4 - BOJ

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

23971번: ZOAC 4

 

이 문제는 프로그래머스 "거리두기 확인하기"와 상당히 비슷하다

https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

 

그러나 BFS를 사용해 제대로 앉았는지 확인하는 거리두기 확인하기 문제와 달리 총 몇명이 앉아야하는지 계산하는 문제다.

나는 이 문제를 당연히 BFS로 풀려 시도했었다.

from collections import deque

h, w, n, m = map(int, input().split())

arr = [[0 for _ in range(w)] for _ in range(h)]

arr[0][0] = 1

# arr.append((0, 0, ))

q = deque()
q.append((0, 0, 0, 0))

dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

result = 0
while q:
    x, y, top_x, top_y = q.popleft()

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

        if 0 <= nx < h and 0 <= ny < w:
            if arr[nx][ny] == 0:

                if (abs(top_x - nx) > n) or (abs(top_y - ny) > m):
                    arr[nx][ny] = arr[x][y] + 1
                    q.appendleft((nx, ny, nx, ny))
                    result += 1

                else:
                    arr[nx][ny] = arr[x][y]
                    q.append((nx, ny, top_x, top_y))

print(result)

그러나 빈번히 실패했다.

이 문제는 상당히 쉬웠다.

 

우선 문제를 잘 이해해야한다.

• 자리의 세로와 가로를 넘지 않게 앉아야한다.
• 자리를 앉았다면 그 자리로부터 세로로 N, 또는 가로로 M만큼 떨어져 앉아야 한다.

이 문제조건을 살펴보면 항상 처음 앉는 사람은 1,1(인덱스 0,0)에 앉아야한다.

그럼 가로로 살펴보자

1

2

3

4

5

위와같이 가로로 5자리가 있을때, M이 1이라고 생각해보자.

그럼 첫번째 사람은 1번자리에, 2번째 사람은 3번, 3번째 사람은 5번 자리에 앉을 수 있다. (3명)

같은 표에서 M이 2라고 생각해보자. 

그럼 1, 3만 앉을 수가 있다. (2명)

3칸을 띄어야한다면 1과 5를 앉을 수가 있다. (2명)

W가 5, M이 1이라 했을때 3이 나오려면, 또는 M이 2나 3에서 앉아야 할 사람이 2명이 나오려면,

자리의 가로 길이 / (M + 1)에서 올림을 진행하면 된다.

세로 또한 마찬가지이다.

H,W,N,M = list(map(int,input().split(' ')))
#math.ceil()함수는 숫자의 올림을 계산해 줍니다
import math
a = math.ceil(H/(N+1)) # 세로에 몇 명이 앉는지를 계산합니다
b = math.ceil(W/(M+1)) # 가로에 몇 명이 앉는지를 계산합니다
answer = a*b #가로와 세로의 값을 곱합니다
print(answer)

단순한 계산, 그것도 DP문제도 아닌 문제로 끙끙 앓아먹다니... 너무 슬프다..