import sys
from collections import deque
input = sys.stdin.readline
def bfs(point,dis_list,flag):
dis_list[point[0]][point[1]] = arr[point[0]][point[1]]
dx = [-1,0]
dy = [0,1]
stack = deque()
stack.append((point[0],point[1]))
while stack:
x,y = stack.popleft()
for i in range(2):
nx = x + dx[i]
ny = y + dy[i]*flag
if 0<=nx<N and 0<=ny<M:
if dis_list[nx][ny] < dis_list[x][y] + arr[nx][ny]:
dis_list[nx][ny] = dis_list[x][y] + arr[nx][ny]
stack.append((nx,ny))
N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
INF =float('inf')
start_distance = [[-INF for _ in range(M)] for _ in range(N)]
end_distance = [[-INF for _ in range(M)] for _ in range(N)]
start_point = (N-1,0)
end_point = (N-1,M-1)
bfs(start_point,start_distance,1)
bfs(end_point,end_distance,-1)
max_value = -INF
for i in range(N):
for j in range(M):
if start_distance[i][j] + end_distance[i][j] > max_value:
max_value = start_distance[i][j] + end_distance[i][j]
print(max_value)
이 문제는 저는 BFS를 이용해서 풀었다.(근데 아직 푼사람이 적은지 solved.ac 기준에는 다이나믹 프로그래밍 밖에 없다.)
boj.kr/2206 문제와 비슷한 방식으로 풀었다.
이 문제를 봐보면 상승이나 하강은 특정한 방향으로 밖에 가지 못한다.
이 점을 이용해서 우리는 특정지점 (x,y)까지의 최대값을 bfs를 이용해 갱신할 수 잇을것이다.
그래서 나는 (N-1,0)에서 상승을 시작하므로, 이 지점을 시작으로 갈수 있는 모든지점에 대해, bfs를 돌려 최대값을 갱신을 해주었다.
똑같은 방식으로 (N-1,M-1) 위치로 하강을 해야하므로, 이 위치에서 하강의 반대방향으로 BFS를 돌리면서 최대값을 갱신을 해주었다.
그러면 우리는 상승을 할때의 각 지점의 최대값 하강을 할때의 각 지점의 최대값을 가지고 있는 행렬을 가지게 되었다.
import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())
arr = []
aircon = deque()
visited = [[[True for _ in range(4)] for _ in range(M)] for _ in range(N)]
total_set = set()
for x in range(N):
temp = list(map(int,input().split()))
for y in range(M):
if temp[y] == 9:
aircon.append((x,y,[0,1,2,3]))
temp[y] = 0
total_set.add((x,y))
for i in range(4):
visited[x][y][i] = False
arr.append(temp)
if aircon:
dx = [-1,0,1,0]
dy = [0,-1,0,1]
rotate_dict = {
1 : [0,-1,2,-1],
2 : [-1,1,-1,3],
3 : [3,2,1,0],
4 : [1,0,3,2]
}
# 북,서,남,동
while aircon:
x,y,dire = aircon.pop()
for i in dire:
nx = x + dx[i]
ny = y + dy[i]
while 0<=nx<N and 0<=ny<M and visited[nx][ny][i] and visited[nx][ny][(i+2)%4] and not arr[nx][ny]:
visited[nx][ny][i] = False
visited[nx][ny][(i+2)%4] = False
total_set.add((nx,ny))
nx = nx + dx[i]
ny = ny + dy[i]
if 0<=nx<N and 0<=ny<M and arr[nx][ny]:
if rotate_dict[arr[nx][ny]][i] != -1:
visited[nx][ny][i] = False
visited[nx][ny][(i+2)%4] = False
visited[nx][ny][rotate_dict[arr[nx][ny]][i]] = False
total_set.add((nx,ny))
aircon.append((nx,ny,[rotate_dict[arr[nx][ny]][i]]))
else:
visited[nx][ny][i] = False
visited[nx][ny][(i+2)%4] = False
total_set.add((nx,ny))
print(len(total_set))
else:
print(0)
tony9402님이 1회차 문제들 중에 푸는데 가장 오래걸렸던 문제였다.
처음에 아슬아슬하게 통과했는데, 이 코드 같은경우엔 통과가 될수도 안될수도 있을정도의 커트라인에 걸친 코드이다.
이 첫 풀이의 아이디어는 다음과 같다. N*M*4의 visitied를 만들어놔서, 방문표시를 해주었다.
그리고 방문표시를 할때, 서로 반대되는 경우와 회전을 했을때에는, 반대되는 경우 + 회전하는경우까지 전부 방문 처리를 해주었다.
위와 같은 작업을 하고, BFS를 돌리면서 전체 방문을 한 위치들을 set에 넣어서 길이를 출력해주었다.
import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())
def func(row):
return row.count(True)
arr = []
aircon = deque()
visited = [[False for _ in range(M)] for _ in range(N)]
for x in range(N):
temp = list(map(int,input().split()))
for y in range(M):
if temp[y] == 9:
aircon.append((x,y,[0,1,2,3]))
visited[x][y] = True
arr.append(temp)
if aircon:
dx = [-1,0,1,0]
dy = [0,-1,0,1]
rotate_dict = {
1 : [0,-1,2,-1],
2 : [-1,1,-1,3],
3 : [3,2,1,0],
4 : [1,0,3,2]
}
# 북,서,남,동
while aircon:
x,y,dire = aircon.pop()
for i in dire:
nx = x + dx[i]
ny = y + dy[i]
while 0<=nx<N and 0<=ny<M :
if arr[nx][ny] == 9:
break
visited[nx][ny] = True
if 0<=nx<N and 0<=ny<M and arr[nx][ny]:
if rotate_dict[arr[nx][ny]][i] != -1:
i = rotate_dict[arr[nx][ny]][i]
else:
break
nx = nx + dx[i]
ny = ny + dy[i]
b = sum(list(map(func,visited)))
print(b)
else:
print(0)
깔끔한 풀이는 다음과 같다.
이 풀이는 다음과 같다. 에어컨 바람은 언제 멈추면될것인가 이다.
문제를 읽어보면 에어컨 바람이 멈출 만한 곳은 총 3가지 경우이다.
1. 연구실 범위를 벗어났을때
- 당연하게 연구실 밖으로 바람이 벗어나면 돌아올 방법이 없으므로, 연구실 범위가 벗어났을때, 에어컨 바람은 그만둔다.
2. 다른 에어컨을 만났을때
- 다른 에어컨을 만났을때 왜 멈춰야하는지 의문을 표할수도 있다. 하지만 생각을 해보면, 우리는 어떠한 경로를 통해
A에어컨에서 B에어컨까지 왔다. 그러면 B에어컨에서도 똑같이 A에어컨으로 갈 수 있는 경로가 생긴 것이다.
각 에어컨은 상하좌우로 전부 돌기 때문에, 가능한 것이다. 그러므로 다른 에어컨에 만났을 때, 거기서부터의 바람의 이동은 그 에어컨에서 다시 탐색을 하면 되는 것이다.
3. 물건1,2의 방향과 수직되는 방향의 바람이 들어왔을 때
- 이때는 경우2번을 생각해보면 똑같다. 우리는 특정한 경로를 통해 물건1, 2로 왔을 것이다. 그런데 수직되는 방향으로 바람이 들어오면, 그 바람은 반대로 되돌아 간다. 즉, 우리가 왔던 길로 되돌아가서, 우리가 최초로 바람이 왔던 에어컨으로 돌아간다.
그러면, 그때의 반대방향으로 가는 바람은 우리가 상하좌우를 전부 탐색을 할 것이기때문에, 이미 탐색범위에 있다.
그렇기 때문에 굳이 다시 탐색을 할 필요가 없다.
그러므로 위의 3가지경우를 제외하고는 방향을 계속 전환을 해주면서 방문표시를 해주면된다.
이 방문 표시는 재방문을 방지하기 위한 방문표시가 아니라, 에어컨의 바람이 어디까지 영향을 줬는지 세기 위한 것이다.
그래서 나는 3가지 경우를 제외하고는 계속해서 돌도록 while문을 돌려주었고,
전부 돌리고 난뒤에 visited의 True의 개수를 세어, 출력을 해주었다.
낮은 난이도의 문제였지만, 처음 잘못잡은 아이디어와 접근방법으로 인해 가장 오래걸리고 고생했던 문제였다.
N,X = map(int,input().split())
arr = list(map(int,input().split()))
if max(arr) == 0:
print('SAD')
else:
value = sum(arr[:X])
max_value = value
max_cnt = 1
for i in range(X,N):
value += arr[i]
value -= arr[i-X]
if value > max_value:
max_value = value
max_cnt = 1
elif value == max_value:
max_cnt += 1
print(max_value)
print(max_cnt)
범위 내의 최대 누적자수를 구하면 되는 문제이다.
그래서 나는 슬라이딩 윈도우를 이용해 X의 크기만큼의 첫 방문자수를 구한뒤 한칸씩 이동하면서 더해주고 빼주는 작업을 반복했다.
그리고 값이 갱신되면 1로 초기화를 해주고, 그렇지 않고 최대값과 같은 값이 나왔을때는 더해주는 방식으로 풀 수 있었다.
def get_divide_list(num):
result = []
for i in range(1,int(num**0.5)+1):
if not num%i:
result.extend([i,num//i])
result = list(set(result))
result.remove(1)
return result
N = int(input())
arr = list(map(int,input().split()))
X = int(input())
X_list = get_divide_list(X)
answer = 0
cnt = 0
for num in arr:
for x_num in X_list:
if not num%x_num:
break
else:
answer += num
cnt += 1
print(answer/cnt)
이 문제 또한, 소수를 구하면 된다. 약수를 구할때, 구하고자하는 수의 sqrt만
탐색을 해주면 좀 더 빠르게 할 수 있다는 점을 생각하고 풀면 편한다.
만약 1을 제외한 약수들을 구한뒤, 약수로 나뉘면, 멈추는 방식으로 해서, 평균을 구했다.
import sys
input = sys.stdin.readline
def get_prim_number(input_Num):
last_num = input_Num
visited = [False for _ in range(last_num+1)]
visited[0] = True
visited[1] = True
result = []
for num in range(2,last_num+1):
if not visited[num]:
result.append(num)
for new_num in range(2*num,last_num+1,num):
visited[new_num] = True
return result
N = int(input())
arr = list(map(int,input().split()))
result = []
max_num = max(arr)
prim_set = get_prim_number(max_num)
for val in arr:
if val in prim_set:
result.append(val)
if len(result)>0:
answer = 1
result = set(result)
for prim in result:
answer*=prim
print(answer)
else:
print(-1)
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
arr = list(map(int,input().split()))
cnt = [0]*(N+1)
for _ in range(M):
command,x,y = map(int,input().split())
x -= 1
if command == 1:
arr[x] = y
elif command == 2:
y -= 1
for ind in range(x,y+1):
arr[ind] = (arr[ind]+1)%2
elif command == 3:
y-=1
for ind in range(x,y+1):
arr[ind] = 0
else:
y -= 1
for ind in range(x,y+1):
arr[ind] = 1
print(*arr)
이 문제는 문제에 주어진 조건대로 배열의 상태를 바꿔주면 되는 문제였다.
전체 배열의 크기가 4000이고, 최대 명령이 4000이라,
최악의 경우라 해도 1600만번밖에 안되므로, 문제에 주어진 조건대로 돌리면 되는 문제이다.
import sys
from collections import deque
input = sys.stdin.readline
def calc(i,input_list,flag):
if i == 1:
input_list.rotate(2)
elif i == 2:
input_list.reverse()
input_list.rotate(2)
elif i == 3:
a,b = input_list.popleft(),input_list.popleft()
input_list.insert(1,a)
input_list.insert(3,b)
elif i == 4:
a = input_list.popleft()
input_list.rotate(1)
b = input_list.pop()
input_list.rotate(1)
input_list.append(a)
input_list.append(b)
elif flag and i ==6:
a = input_list.popleft()
input_list.rotate(1)
b = input_list.pop()
input_list.rotate(1)
input_list.append(a)
input_list.append(b)
elif flag and i == 5:
a,b = input_list.popleft(),input_list.popleft()
input_list.insert(1,a)
input_list.insert(3,b)
N,M,R = map(int,input().split())
half_N = N//2
half_M = M//2
arr = [list(map(int,input().split())) for _ in range(N)]
arr_divide = {}
for i in range(4):
temp = []
quo = i//2
mod = i%2
start_x = quo*(N//2)
end_x = (quo+1)*(N//2)
start_y = mod*(M//2)
end_y = (mod+1)*(M//2)
for x in range(start_x,end_x):
tmp = []
for y in range(start_y,end_y):
tmp.append(arr[x][y])
temp.append(tmp)
arr_divide[i+1] = temp
command_cnt = [0 for _ in range(7)]
command_list = list(map(int,input().split()))
small_list = deque([1,2,3,4])
mini_rotate = deque([0,1,2,3])
for i in command_list:
calc(i,small_list,True)
calc(i,mini_rotate,False)
position = [[0,0],[0,M//2-1],[N//2-1,0],[N//2-1,M//2-1]]
one,two,three = mini_rotate.popleft(),mini_rotate.popleft(),mini_rotate.popleft()
for i in range(4):
origin = position[one]
left_origin = position[two]
bottom_origin = position[three]
if origin[0] == left_origin[0] and origin[1] == bottom_origin[1] :
if origin[1] > left_origin[1]:
dy = -1
else:
dy = 1
if origin[0] > bottom_origin[0]:
dx = -1
else:
dx = 1
temp = []
for x in range(abs(bottom_origin[0]-origin[0])+1):
tmp = []
for y in range(abs(origin[1] - left_origin[1])+1):
tmp.append(arr_divide[i+1][origin[0]+x*dx][origin[1]+y*dy])
temp.append(tmp)
arr_divide[i+1] = temp
else:
if origin[0] > left_origin[0]:
dy = -1
else:
dy = 1
if origin[1] > bottom_origin[1]:
dx = -1
else:
dx = 1
temp = []
for x in range(abs(bottom_origin[1]-origin[1])+1):
tmp = []
for y in range(abs(left_origin[0]-origin[0])+1):
tmp.append(arr_divide[i+1][origin[0]+dy*y][origin[1]+dx*x])
temp.append(tmp)
arr_divide[i+1] = temp
last_N= len(arr_divide[1])*2
last_M = len(arr_divide[1][0])*2
result = [[0 for _ in range(last_M)] for _ in range(last_N)]
for i in range(4):
idx = small_list.popleft()
quo = i//2
mod = i%2
start_x = quo*(last_N//2)
start_y = mod*(last_M//2)
my_array = arr_divide[idx]
for x in range(last_N//2):
for y in range(last_M//2):
result[start_x+x][start_y+y] = my_array[x][y]
for x in range(last_N):
for y in range(last_M):
print(result[x][y],end=' ')
print()
배열 돌리기 시리즈의 5번째이다.
이 배열돌리기는 전체를 돌리면 무조건 시간초과가 날수밖에 없다.
왜냐하면 최대 100*100의 행렬이 오는데 그걸 200만번 수행을 하면 터질수 밖에 없다.
그렇다 면 이 문제를 해결하는 방법은 다음과 같다.
이 문제에서 행렬을 크게 4부위로 나눌수 있다.
처음 배열을 다음과 같이 4등분을 해주자(문제에서는 1 2/ 3 4 가 아니라, 1 2 / 4 3 형태이지만, 그냥 편하대로 하면 된다.)
그러면 1번 돌리기는 다음과 같이 표현할 수 있다.
위 아래의 배열이 바뀌고, 그리고 그안의 있는 값도 상하반전이 된 것을 알 수 있다.
2번 돌리기는
좌우 반전이 되고, 그리기 도구에서 안의 숫자를 좌우반전을 하는게 없어서 표현 못했지만, 그 안에 있는 작은 배열들도 좌우 반전이 되어야한다.
3번 돌리기는
오른쪽으로 90도 돌면서 그 안의 있는 값들도 90도로 돌리면 된다.
4번 돌리기는 왼쪽으로 90도로 돌리고, 그 안의 배열들도 같이 왼쪽으로 90도를 돌리면 된다.
5번 돌리기는 3번돌리기와 똑같이 전체 배열의 이동은 같지만, 안의 배열이 돌아가지 않는 모습이다.
그리고 6번 돌리기는 4번돌리기와 전체배열의 이동은 같지만 안의 배열이 돌아가지 않는 모습이다.
이렇게 4등분을 해보면 우리는 알 수 있는 사실이 있다.
전체 배열을 전부 돌릴필요가 없다는 것이다.
1~6번 돌리기를 간략하게 표현할 수 있는 2*2 배열을 돌리기만 하면 된 다는 것을 알 수 있다.
그러면 그 안에 있는 배열들이 돌아가는 것은 어떻게 표현하느냐이다.
위와 같이 한 배열이 있다고 하면, 우리는 네 꼭지점의 위치를 알면 전체 배열이 어떻게 모양이 변한지 알 수 있다.
이러한 특성을 이용해서
mini_rotate에는 각 꼭지점의 위치를 표현한 (0,1,2,3)을 상황에 맞게 돌려주면서, 작은 배열에서 1~4번 돌리기에 해당될때 어떻게 회전되는지를 표현해주었다.
그리고 small_list는 전체 배열을 4등분을 해서, 각 등분된 배열을 1,2,3,4로 매칭시키고, 1~6번 돌리기에 맞게 회전을 시켜 주었다.
mini_rotate를 돌릴때 주의 해야할 것은 나는 행을 x 열을 y로 표현하는 편이다. 돌리다 보면
행과 열이 뒤바뀌어서 행이 dy 열로 이동하는 것이 dx로 뒤바뀔때가 있을 것이다.
그러면 이걸 어떻게 구분할 것이냐,
위의 변수명을 잘못 선언했지만 다음과 같다.
원본 배열에서 (0,0) 이 부분을 origin이라 하겠다.
그리고 (0,M//2) 이부분을 right_origin(코드에서는 left_origin) 이라 부르겠다.
그리고 (N//2,0) 이 부분을 bottom_origin이라 부르겠다.
그러면 우리가 전부 회전을 하고 난뒤에 바뀐 위치에 있는 origin, right_origin, bottom_origin이 있을것이다.
