[파이썬] 백준 23971 - ZOAC 4

23971번: ZOAC 4

 

문제를 보고 h*w 크기의 0으로 초기화 된 리스트를 만들고 리스트에서 2중 for문으로 n+1, m+1간격의 값을 1로 변경하려고 했다.

그 뒤 총 합을 구하면 정답이라고 생각했다.

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

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


for i in range(0, h, n+1):
    for j in range(0, w, m+1):
        if i < h and j < w:
            if people[i][j] == 0:
                people[i][j] = 1


total_sum = sum([sum(row) for row in people])

print(total_sum)

 

이렇게 하니까 메모리 초과가 떴다.

 

코드를 살펴보니 문제점이 보였다.

->  total_sum을 나중에 총합 계산하지 않고 미리 선언 후 증가하는 방식으로 구하고자 생각했다.

 

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

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

for i in range(0, h, n+1):
    for j in range(0, w, m+1):
        if i < h and j < w:
                total_sum += 1


print(total_sum)

 

그런데도 메모리 초과가 발생했다.

다시 코드를 보니 초기 people이 사용되지 않음을 깨닫고 지우고 제출하니 시간초과가 떴다.

 

그래서 이중 for문을 사용하지 않고 코드를 짜려고 했다.

어차피 for문의 역할이 단순 사칙연산의 역할이었으므로

 

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

row = (h-1) // (n+1) +1
col = (w-1) // (m+1) +1

print(row*col)

 

이렇게 for문의 역할을 사칙연산으로 나타내었다.

 

그 결과 맞았습니다!가 떴다.

 

---

문제를 보고 어떤 방식으로 풀면 가장 최적화된 방식일지 미리 생각을 더 하고 구현을 해보자!!

그리고 최대한 for문과 자료구조를 쓰지 않는 간결화된 방식을 지향하자.