Python

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42895 문제 해설 Idea Dynamic Programming S[1] = {N} S[2] = {NN, N+N, N-N, N*N, N/N} S[3] = {NNN, S[2] (+,-,*,/) S[1][y], …} 2부터 8까지의 범위를 가진 i와 1부터 i-1까지의 범위를 가진 j에 대해, S[j]와 S[i-j]의 사칙연산 결과를 S[i]에 추가하고 해당 집합이 number를 포함하는지 검증 Time Complexity DP: O(1) Data Size N: 1 <= int <= 9 number: 1 <= int <= 32,000 answer: int <= 8 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 from itertools import product def solution(N, number): S = [set() for _ in range(9)] if N == number: return 1 else: S[1]....

문제 링크 https://www.acmicpc.net/problem/21318 문제 해설 Idea Prefix Sum 실수한 곡에 대한 누적합을 구하고 인덱싱을 통해 특정 구간에 대한 누적합 출력 마지막 곡은 항상 성공하기 때문에 y에 대한 누적합과 y-1에 대한 누적합이 다르면 1 감소 Time Complexity Prefix Sum: O(N) = 100,000 Data Size N: 1 <= int <= 100,000 scores: int(10^9) * N Q: 1 <= int <= 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys input = sys....

문제 링크 https://www.acmicpc.net/problem/16987 문제 해설 Idea Backtracking 0번째 계란부터 마지막 계란까지의 모든 경우의 수를 탐색 시간 단축을 위해 현재 계란이 깨진 경우 또는 나머지 모든 계란이 깨진 경우를 예외로 처리 한 번에 두 개 이상의 계란을 치는 경우를 방지하기 위해 계란을 친 후 원상복구 수행 Time Complexity Backtracking: O(N^N) = 16,777,216 Data Size N: 1 <= int <= 8 S, W: 1 <= int <= 300 해설 코드 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 N = int(input()) eggs = list() for _ in range(N): eggs....

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