🧩 문제
🧩 문제 해석
- n은 무조건 홀수이기 때문에, 0번째 줄에서는 무조건 1개의 사과나무로 시작한다.
- 1, 3, 5.. 홀수의 개수만큼 사과나무가 늘어난다.
- n개의 사과가 선택되는 줄 다음에는 다시 홀수의 개수만큼으로 사과나무가 줄어든다.
🏁 내 풀이
n = int(input())
apples = [list(map(int, input().split())) for _ in range(n)] # 2차원 배열로 N * N 받기
get = 0
for i in range(n):
if i <= n//2: # 다이아몬드 윗부분
# 차례로 홀수 만큼 늘어남
get += sum(apples[i][(n // 2) - i:(n // 2) + i+1])
else: # 다이아몬드 아래부분
# 차례로 홀수 만큼 줄어듦
get += sum(apples[i][- (n + n // 2) + i:(n // 2) - i])
print(get)
- 시간복잡도: O(N)
- 0번째 줄의 값은 n[n//2] 인덱스 값이므로
n//2번째 줄의 row가 n개가 될 때까지는 i만큼 늘어날 수 있게 작성했다. - n개의 row를 지나면 다시 홀수씩 줄어들어야 하므로, [-4:-2], [-3:-3] 이런 식으로 알고리즘이 나오게 슬라이싱했다.
🏁 풀이
# 인프런 풀이
a = [list(map(int, input().split())) for _ in range(n)]
res = 0
s=e=n//2
for i in range(n):
for j in range(s, e+1):
res += a[i][j]
if i < n//2: # 다이아몬드 윗부분
s -= 1
e += 1
else: # 다이아몬드 아래부분
s += 1
e -= 1
- 시간복잡도: O(N^2)
- s(슬라이싱 앞의 값)와 e(슬라이싱 뒤의 값)를 따로 설정하여 사과나무의 개수가 n이 됐을 때의 전후를 다르게 계산했다.
Engineer