23971. ZOAC 4
접근 방식
1️⃣ 추가할 수 있는 인원 수를 모두 배열에 저장하고, 최대값 뽑기 (메모리 초과)
정답을 알고 나서 첫번째 접근 방식은 너무 어렵게 문제에 접근하려다가 제대로 꼬여버린 것 같았다... 좌표 값 x, y를 뽑기 위해서 for문을 사용했으면 되었을 것을, product를 사용해서 풀어보려고 했다. (좌표 조합의 데카르트곱 결과를 가져올 필요가 있었을까 싶은 풀이)
현재의 좌표로부터 가로, 세로 차이가 M, N만큼 나는 좌표가 생기면 cnt값을 누적하고, 최종적으로 최대한으로 수용 가능한 인원의 수를 관리하는 ans 배열에 추가하는 로직으로 생각했다.
메모리 초과가 나왔고! 로직 자체도 처음 product를 사용해서 풀어야겠다는 고집때문에 점점 산으로 갔었던 듯?!
# 메모리 초과
import sys
from itertools import product
input = sys.stdin.readline
H, W, N, M = map(int, input().rstrip().split())
candidates = [[i+1 for i in range(W)], [i+1 for i in range(H)]]
res = list(product(*candidates)) # 나올 수 있는 좌표 조합 데카르트곱으로 만들기
ans = [] # 인원 수 저장 배열
for i in range(len(res)):
cnt = 0 # 인원수 누적 카운터
x, y = res[i][0], res[i][1]
for j in range(i+1, len(res)):
nx, ny = res[j][0], res[j][1]
if nx - x > M and ny - y > N:
cnt += 1
else:
continue
ans.append(cnt)
print(max(ans))2️⃣ 그리디로 접근(메모리 초과)
최대로 수용 가능한 인원을 뽑는 것이기에, 1번 방식은 완전 탐색이었다면 그리디로 첫번째 학생의 좌표가 정해지면 그 좌표값을 기준으로 다음 좌표를 탐욕적으로 선택하는 그리디를 생각했었다.
그래서 스택의 LIFO 구조를 사용해 구현하였으나... 이 또한 메모리 초과...
최종 코드
정답 코드를 보고 머리가 조금 띵했던 문제다.....
예를 들어 예제처럼 W : 4, H : 5, M : 1, N : 1의 상황을 가정해보자.
한 열을 기준으로 보았을 때,
O X O X O -> 5개의 칸 중 3명이 1개의 칸을 간격으로 앉음 : 5 / (1 + 1) = 2.5
O X X O X -> 5개의 칸 중 2명이 2개의 칸을 간격으로 앉음 : 5 / (2 + 1) = 1.66
O X X X O -> 5개의 칸 중 2명이 3개의 칸을 간격으로 앉음 : 5 / (3 + 1) = 1.25
O X X X X -> 5개의 칸 중 1명이 4개의 칸을 간격으로 앉음 : 5 / (4 + 1) = 1
즉, 테이블의 개수 / (거리두기 간격 + 1)으로 계산해 이를 반올림하면 최대로 앉을 수 있는 학생 수를 구할 수 있다.
import sys, math
input = sys.stdin.readline
H, W, N, M = map(int, input().rstrip().split())
row = math.ceil(W / (M + 1))
col = math.ceil(H / (N + 1))
print(row * col)math 라이브러리의 반올림 값을 구하는 ceil 함수를 사용하면 무려 5줄 내외로 맞출 수 있는 문제였다. 더불어 위에서 여러개의 리스트로 메모리를 남용하였던 내 코드와 달리, 변수 몇개만의 메모리 사용으로 풀이할 수 있었다.
행과 열 각각 ceil 함수 사용을 통해 값을 구한 뒤 마지막에 곱해주기!
배운점
1️⃣ 파이썬에서 제공되는 라이브러리 중에 사용할 수 있는 것이 뭐가 있을지 잘 생각해보기
2️⃣ 어렵게 접근하거나 특정 알고리즘 적용할 생각을 하기 전에, 쉬운 방법으로 풀이할 수는 없을지 깊게 생각해보기
3️⃣ 조금만 시도하다가 답안 찾게되는 나쁜 습관 고쳐!!!!
