[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-7 "사과나무(다이아몬드)"
[시간복잡도]
O(N²) : 이중 for문을 사용했다.
[공간복잡도]
O(N)
Problem
현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저 있다.
N의 크기는 항상 홀수이다. 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사 과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다.
만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다.
현수과 수확하는 사과의 총 개수를 출력하세요.
▣ 입력설명
첫 줄에 자연수 N(홀수)이 주어진다.(3<=N<=20)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다.
이 자연수는 각 격자안에 있는 사과나무에 열린 사과의 개수이다.
각 격자안의 사과의 개수는 100을 넘지 않는다.
▣ 출력설명
수확한 사과의 총 개수를 출력합니다.
▣ 입력예제
5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19
▣ 출력예제
379
💯 Solution ①
: 코드에 대한 로직은 튜터님의 코드와 동일하게 생각했지만, 코드 구현을 하는 과정에서 구현을 못해서 튜터님의 코드를 참고했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import sys
sys.stdin=open("input.txt","rt")
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
res=0
s=e=n//2
for i in range(n):
# s부터 e까지 돌기
for j in range(s,e+1):
res+=a[i][j]
# i가 n//2보다 작아질 때
if i<n//2:
# 시작점은 한칸을 빼고, 끝점은 한칸을 늘린다.
s-=1
e+=1
# i가 n//2보다 클 때
else:
# 시작점을 한칸을 늘리고, 끝점을 한칸씩 줄인다.
s+=1
e-=1
print(res)
|
cs |
- a : [[]], 이중 리스트 형태로 이루어진 리스트
- res : 초기값으로는 0을 배정하고, res에는 해당 배열의 값들을 모두 더한다.
=> 첫 for문을 통해서, a의 모든 배열을 돈다.
=> 그리고 두 번째 for문을 통해서 해당 배열에서 시작점과 끝점 사이에 있는 값들을 res에 더한다.
- 그리고 만약 기준점인 n//2 보다 i가 작다면, s-=1 / e+=1 을 통해서 칠해지는 행의 범위를 넓힌다.
- 만약 if조건에 해당하지 않는다면, s+=1 / e-=1 을 통해서 칠해지는 행의 범위를 좁힌다.
💯 Solution ②
: Tutor's Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import sys
sys.stdin=open("input.txt","rt")
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
res=0
s=e=n//2
for i in range(n):
# s부터 e까지 돌기
for j in range(s,e+1):
res+=a[i][j]
# i가 n//2보다 작아질 때
if i<n//2:
# 시작점은 한칸을 빼고, 끝점은 한칸을 늘린다.
s-=1
e+=1
# i가 n//2보다 클 때
else:
# 시작점을 한칸을 늘리고, 끝점을 한칸씩 줄인다.
s+=1
e-=1
print(res)
|
cs |