문제 정보
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB
접근방법
수확은 정사각형 마름모 형태로만 가능하다!
=> 마름모를 체크하기 어려우니 삼각형으로 나누자!
1차 풀이(미제출)
농장의 크기를 벗어나서 수확할 수 없다!
=> 농장의 범위를 잘 체크하자
주어진 사진을 잘 관찰하다 보니 규칙을 찾을 수 있었다.
정사각형 농장의 가로 중앙은 늘 농장의 끝까지 농작물을 수확할 수 있다는 것이다.
그래서 수확범위를 아래와 같이 세등분 하기로 했다.
상단 삼각형
중강 가로값
하단 삼각형
garo = 0
dr = [0, 0]
dc = [-1, 1]
start = end = n//2
for d in range(2):
for k in range(1, n):
nr = start + dr[d] * k
nc = end + dc[d] * k
if 0 <= nr < n and 0 <= nc < n:
garo += bap[nr][nc]
가로 중앙 수확값을 찾아주기 위해 좌, 우로 이동하는 델타를 사용했다.
밭의 정 중앙에서 시작하기 위해 시작, 마지막 값을 전체 농장 범위를 2로 나눈 몫으로 잡았다.
가로 중앙은 농장의 마지막 까지 수확 가능하기 때문에 범위를 1 ~ n-1 까지 잡고 값을 곱했다.
수확은 농장의 범위를 벗어날 수 없기 때문에 최대값을 벗어나지 않게 설정해줬다.
여기까지 하고 상단 삼각형과 하단 삼각형의 값을 찾아주는데서 막혔다.
2차 풀이는 지금까지 했던 생각을 싹 뒤집어 엎고 진행했다.
2차 풀이(통과)
def UPR():
global hap
for i in range(start, mid+1): #가장 위쪽 중앙부터 아래로 한칸씩 증가하면서 삼각형을 이룸
for j in range(mid - i, n - mid + i):
hap += filed[i][j]
return hap
def DNR():
global hap
global start
for r in range(end, mid, -1): # -1씩 감소하면서 중앙선 바로 아래까지 하락
for c in range(mid - start, mid + 1 + start):
# 아래로 한칸 내려갈때마다 왼쪽은 1씩 감소 오른쪽은 1씩 증가 필요
hap += filed[r][c]
start += 1 # for c 가 끝나면 시작점을 1씩 증가시킨다
return hap
for test in range(int(input())):
n = int(input())
filed = [list(map(int, input())) for _ in range(n)]
start = 0
mid = n//2
end = n - 1
hap = 0
UPR()
DNR()
print(f'#{test + 1} {hap}')
1차 방식과 접근방법 자체는 동일하지만
중앙 가로값을 따로 체크하지 않았다.
상단 삼각형의 범위를 중앙 가로값까지로 제한해서 한번에 중앙까지 값을 찾을 수 있게 해 주었다.
하단 삼각형은 제일 아래 중앙에서 시작해서 위로 한칸씩 하락 하면서 값을 체크할 수 있게 해주었다.
하락에서 가장 고민한 부분은 탐색범위를 어떻게 좌 - 우 한칸씩 증가시킬 수 있을까 하는 점이였는데
아래의 for 문을 전부 순회하면 strart 를 1씩 증가시켜주면서 좌우 한칸씩 더 측정할 수 있게 해주었다.
end 를 n - 1 처리 해준 이유는 인덱스 범위를 벗어나지 않게 해주기 위해서이다.
느낀점
개인적으로 별찍기 문제를 정말 싫어해서 많이 풀려하지 않았었는데 그 업보가 돌아온 느낌이다.
방향델타를 이용해서 상하좌우 대각선 측정하는 방식이 많이 익숙해진 것 같다.
이 방법으로 문제를 해결하지는 못했지만 최종적으로 해결한 방식을 적용하면 델타를 사용해서
중앙 가로값을 계산하는 방법도 불가능하지는 않았을 것 같다.
문제가 잘 풀리지 않을 땐 생각을 리셋하는법도 나쁘지 않다는것을 느꼈다.
집에 도착해서 골아떨어진 이후에 비몽사몽한 상태에서 문제를 풀어서 더욱 그랬겠지만
다음날 강의실에서 말끔한 정신으로 문제를 해결했더니 금방 풀었다.