dukim's blog

문제 https://www.acmicpc.net/problem/17409 17409번: 증가 수열의 개수 첫째 줄에 N, K가 주어진다. 둘째 줄에 수열 A1, A2, ..., AN이 주어진다. www.acmicpc.net 설명 가장 긴 증가하는 부분 수열 문제는 파이썬 풀이가 있지만, 증가 수열의 개수(17409)는 파이썬 풀이를 찾으려고 해도 찾기가 힘들어서 lastknight00님의 포스트를 참고하여 Python 코드로 작성하였습니다. N이 작은 경우에는 DP를 이용한 풀이가 가능하지만 시간복잡도가 O(N^2)으로 위 문제의 조건(1

문제 www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 내 풀이 - 백준 연구소 문제와 비슷 - 벽을 설치하는 모든 경우의 수를 찾은 뒤(DFS, BFS, 또는 파이썬 combinations), - 각 경우마다 학생이 걸리는지 여부를 체크해 걸리지 않는 경우 'YES'를 출력 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354..

문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 내 풀이 바이러스가 있는 지점에서부터 BFS 수행, 이 떄 낮은 번호부터 시작하도록 정렬하여 시작할 것 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 from collections import deque n..