백준 실버

문제 링크 https://www.acmicpc.net/problem/16918 문제 해설 Idea Simulation (or BFS) 초기에 빈 칸(.)을 0, 폭탄이 있는 칸(O)을 1로 설정 처음에 폭탄이 있는 칸의 상태를 우선 1 증가시키고, 이후 모든 칸의 상태를 1씩 증가시키는 과정 반복 매번 각 칸의 상태를 점검하면서 3을 초과할 경우 해당 위치 및 이웃 위치를 폭발 대상에 추가 폭발 대상이 존재할 경우 격자의 범위를 벗어나지 않는 범위 내에서 상태를 0으로 변환 위 과정을 N초 동안 반복하고, 0은 빈칸으로, 나머지는 O로 표시하여 출력 Time Complexity Simulation: O(N^3) = 8,000,000 Data Size R, C, N: 1 <= int <= 200 해설 코드 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 import sys input = sys....

문제 링크 https://www.acmicpc.net/problem/2302 문제 해설 Idea Dynamic Programming 자리를 옮길 수 있는 연속되는 좌석의 수는 피보나치 수열을 따름 (S[i] = F[i+1]) VIP 좌석 번호를 기준으로 연속되는 좌석의 수를 리스트로 저장 모든 연속되는 좌석 수에 대한 피보나치 수를 곱하고 출력 Sequence S2 (1,2) -> (1,2), (2,1) = 2(F3) S3 (1,2,3) -> (1,2,3), (2,1,3), (1,3,2) = 3(F4) S4 (1,2,3,4) -> (1,2,3,4), (2,1,3,4), (1,2,4,3), (1,3,2,4), (2,1,4,3) = 5(F5) S5 (1,2,3,4,5) -> (1,2,3,4,5), (1,2,4,3,5), (1,2,3,5,4), (2,1,3,4,5), (2,1,4,3,5), (2,1,3,5,4), (1,3,2,4,5), (1,3,2,5,4) = 8(F6)...

문제 링크 https://www.acmicpc.net/problem/18352 문제 해설 Idea BFS 시작 노드 X부터 연결된 노드를 순차적으로 방문하면서 X로부터 떨어진 거리를 기록 거리가 K와 같은 노드를 출력하고, 해당하는 노드가 없을 경우 -1을 출력 거리가 K를 넘어가지 않는 노드에 대해서만 탐색하여 시간 단축 Time Complexity BFS: O(N+M) = 1,300,000 Data Size N: 2 <= int <= 300,000 M: 1 <= int <= 1,000,000 K: 1 <= int <= 300,000 X: 1 <= int <= N A, B: 1 <= int <= N 해설 코드 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/1495 문제 해설 Idea Dynamic Programming P[i] = max(P[i-1]+V[i-1],P[i-1]-V[i-1]), 0 <= P[i] <= M 모든 P[i-1]가 P[i+1]에 영향을 줄 수 있기 때문에 범위 내 모든 값을 집합에 저장 마지막 곡에 대한 P가 존재할 경우 최댓값을 출력하고, 없을 경우 -1을 출력 Time Complexity DP: O(NM) = 50,000 Data Size N: 1 <= int <= 50 M: 1 <= int <= 1,000 S: 0 <= int <= M V: int * N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 N, S, M = map(int, input()....

문제 링크 https://www.acmicpc.net/problem/2805 개요 이분 탐색으로 해결할 수 있는 문제이다. Python3을 사용하면 시간초과가 발생하므로 PyPy3를 사용한다. 문제 조건 일정 높이에 대해 모든 나무를 잘랐을 때, 조건을 만족하는 절단기의 최대 높이(H)를 구하는 문제이다. 잘린 나무의 길이의 합은 상근이가 필요로 하는 나무의 길이(M)보다 크거나 같아야 한다. 문제 해설 나무의 수(N)의 최댓값이 1,000,000이므로 모든 범위에 대해 반복하는 순차 탐색을 이용할 경우 시간초과가 발생한다. 시간 복잡도가 O(log n)인 이분 탐색을 이용하면 시간 복잡도가 O(n)인 순차 탐색을 쓰는 것보다 훨씬 빠르다....