문제 링크 https://www.acmicpc.net/problem/10026 문제 해설 Idea 모든 방문하지 않은 칸에 대해 BFS 탐색하면서 같은 구역을 방문 적록색약의 경우 R과 G를 같은 구역으로 판단하고 탐색 각각의 경우에 대한 BFS 호출 횟수를 서로 다른 구역의 수로 판단하여 출력 Time Complexity BFS: O(N^2) = 10,000 Data Size N: 1 <= int <= 100 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from collections import deque import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/21758 문제 해설 Idea 벌이 같은 방향을 향하는 경우 상자까지의 총합에서 두 벌의 시작 위치에 있는 값을 제외 벌이 다른 방향을 향하는 경우 상자까지의 총합에 절댓값을 취해서 더함 Data Size N: 3 <= int <= 100,000 arr[i]: 1 <= int <= 10,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 N = int(input()) arr = list(map(int, input().split())) forward, backward = [arr[0]]+[0]*(N-1), [0]*(N-1)+[arr[-1]] for i in range(1,N): forward[i] = forward[i-1] + arr[i] backward[N-i-1] = backward[N-i] + arr[N-i-1] answer = 0 for i in range(1,N-1): answer = max(answer, forward[N-1]*2-forward[0]-forward[i-1]-arr[i]*2) answer = max(answer, backward[0]*2-backward[N-1]-backward[N-i]-arr[N-i-1]*2) answer = max(answer, forward[i]-arr[0]+backward[i]-arr[-1]) print(answer)
문제 링크 https://www.acmicpc.net/problem/5547 문제 해설 Idea 전체 좌표 평면의 외곽에 1만큼의 여백을 추가하고 x,y 좌표가 0부터 시작한다고 판단 y가 홀수 일 때, 인접한 좌표는 상하좌우와 함께 우상단,우하단을 포함 y가 짝수 일 때, 인접한 좌표는 상하좌우와 함께 좌상단, 좌하단을 포함 건물이 없는 좌표를 BFS 탐색하면서 건물과 만나는 지점을 카운트 Time Complexity BFS: O(N^2) = 10,000 Data Size W, H: 1 <= int <= 100 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 from collections import deque import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/1308 문제 해설 Idea 각각의 날짜에 대한 문자열을 date 타입으로 변환하고, today 기준 1000년 후 날짜와 dday를 비교 조건이 맞을 경우 ‘gg’를 출력하고, 아니면 두 날짜의 차이를 출력 Data Size y,m,d: 1,1,1 <= int*3 <= 9999,12,31 해설 코드 1 2 3 4 5 6 7 from datetime import date strptime = lambda: date(**{k:int(v) for k,v in zip(['year','month','day'],input().split())}) today, dday = strptime(), strptime() if dday >= today.replace(today.year+1000): print('gg') else: print('D-'+str((dday-today)....
문제 링크 https://www.acmicpc.net/problem/7569 문제 해설 Idea BFS 7569번 토마토 문제에서 하나의 차원이 추가된 버전입니다. 차원이 늘어난만큼 N의 최대 길이가 감소했기 때문에 여전히 BFS로 해결할 수 있습니다. 익은 토마토의 기준에서 전체 상자를 BFS로 완전탐색하면서 안익은 토마토까지의 최소 거리를 기록합니다. 최소 거리의 최댓값이 곧 토마토들이 모두 익는 최소 일수이며, 모든 토마토가 다 익었을 경우에 최소 일수를 출력하고, 그렇지 않은 경우엔 -1을 출력합니다. Time Complexity O(N^3) = 1,000,000 Data Size M,N: 2 <= int <= 100 H: 1 <= int <= 100 t in [1,0,-1] 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 from collections import deque import sys input = sys....