[구름][알고리즘 먼데이][2주차] 폭탄구현하기 : 파이썬(python)

 

알고리즘 먼데이 챌린지 2주차 폭탄구현하기  (⭐⭐)

 

https://level.goorm.io/exam/159666/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EB%A8%BC%EB%8D%B0%EC%9D%B4-%ED%8F%AD%ED%83%84-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0/quiz/1

구름LEVEL

 

---

 

 

폭탄이 떨어진위치들이 주어졌을 때 전체 폭탄값들의 합을 출력하는 간단한 문제이다.

 

✅ 풀이 과정

1. 복잡도 고려

정사각형의 한변의 길이 n : 1<=n <=20

떨어트릴 폭탄의 개수 k : 1<=k<=500000

 

이므로 

최악의 케이스는 : n =20 , k = 500000 

 

폭탄값 증가 = 500000(폭탄) * 4(상하좌우) = 2000000

전체 폭탄값 합하기 = 20(정사각형 row반복 ) * 20(각 row의 sum구해주기)  = 400

 2000400는  그렇게까지 시간복잡도가 크지 않아서 생각나는대로 구현해줘도 될 것 같다. 

 

 

2. 수도코드

1) for문으로 폭탄의 위치(row, column)을 입력받는다. 배열은 0부터 시작하므로 입력받은 값들을 1 감소시킨다. 

2) 입력받은 위치(row,column)의 폭탄값을 1 증가시킨다.

3) for 문으로 4번 반복, pos로 상 하 좌 우 의 새로운 row column값을 만든다. 해당위치가 유효한 범위이면 폭탄값을 1 증가시킨다. 

4) 전체 폭탄값의 합을 구해야하므로 더해주고, 출력한다. 

 

 

✅ 정답코드

 

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
arr = [[0]*n for _ in range(n)]
pos = [[0,1],[0,-1],[1,0],[-1,0]]

for _ in range(k):
	a, b = map(int, input().split())
	a, b = a-1, b-1
	arr[a][b] +=1 
	
	for i in range(4):
		da = a + pos[i][0]
		db = b + pos[i][1]
		
		if (0<=da<n) and (0<=db<n):
			arr[da][db] += 1
	
result = 0
for li in arr:
	result += sum(li)
	
print(result)