Python

문제 링크 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....

문제 링크 https://www.acmicpc.net/problem/7576 문제 해설 Idea BFS를 활용한 시뮬레이션을 통해 모든 토마토가 익을 떄까지 걸리는 최소 기간을 계산 초기엔 안익은 토마토의 기준에서 매번 익은 토마토까지의 최단거리를 탐색하여, O(N^4)의 시간 복잡도로 시간 초과가 발생 이후 익은 토마토의 기준에서 시뮬레이션을 단 한번만 수행하여 각각의 칸에 도달하는데 걸리는 거리값을 갱신 모두 익지 못하는 상황에 대해 1안에선 에러를 발생시켜 처리했고, 2안에선 종료 코드를 실행해 처리 Time Complexity O(N^2) = 1,000,000 Data Size M,N: 2 <= int <= 1,000 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 from collections import deque import sys input = sys....