문제
https://www.acmicpc.net/problem/1895
Algorithm
주어진 배열을 입력받아 3*3내에서의 T값보다 크거나 같은 것의 개수를 출력하면 된다. 주어진 배열이 40이하의 자연수 이므로 최대 38*38개수의 필터가 있고, 필터 내에서 중앙값을 구하는데, 이때 9개의 원소를 정렬하는 것이므로 9log9정도의 시간복잡도를 가진다. 38*38*9log9 = 약12996이므로 브루트포스로 풀 수 있다고 생각했다!
먼저 배열의 크기 R,C를 입력받은 후에 배열의 원소를 입력받고, T값을 입력받는다. 3*3필터를 적용하기 위해 반복문을 실행해서 그 안의 원소들을 arr에 append하고, arr을 정렬해준다. 9개의 원소의 중앙값은 arr[4]이므로 arr4가 T보다 크면 cnt에 더해주고 마지막으로 cnt를 출력해주면 된다!
Code
input = __import__('sys').stdin.readline
r,c = map(int,input().split())
arr=[]
temp = []
for i in range(r):
arr.append([*map(int,input().split())])
t = int(input())
cnt=0
for i in range(r-2):
for j in range(c-2):
temp.append(arr[i][j])
temp.append(arr[i][j+1])
temp.append(arr[i][j+2])
temp.append(arr[i+1][j])
temp.append(arr[i+1][j+1])
temp.append(arr[i+1][j+2])
temp.append(arr[i+2][j])
temp.append(arr[i+2][j+1])
temp.append(arr[i+2][j+2])
temp.sort()
if temp[4] >= t:
cnt+=1
temp=[]
print(cnt)
'Koala - 10기 > 기초 알고리즘 스터디' 카테고리의 다른 글
Baekjoon 13235번: 팰린드롬 / C++ (0) | 2023.05.07 |
---|---|
[백준 / Python] #11728 배열 합치기 (0) | 2023.05.07 |
[백준/C++] 15813번: 너의 이름은 몇 점이니 (0) | 2023.04.02 |
[백준/Python] 1371번 가장 많은 글자 (0) | 2023.03.31 |
[백준/Python] 3474번 교수가 된 현우 (0) | 2023.03.29 |