본문 바로가기

Python262

[백준 17141번] 연구소 2 https://www.acmicpc.net/problem/17141# 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.# 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.# 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸# 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.# 연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력# 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력import sysfrom collections import dequeinput = sys.stdin.readlineN, .. 2024. 10. 1.
[백준 15989번] 1, 2, 3 더하기 4 import sysinput = sys.stdin.readlinet = int(input())dp = [1]*10001for i in range(2,10001): dp[i] += dp[i-2]for i in range(3,10001): dp[i] += dp[i-3]for i in range(t): print(dp[int(input())]) 이번 문제는 주어진 숫자를 1, 2, 3을 사용하여 만들 수 있는 경우의 수를 구하는 문제이다. 1부터 10까지의 케이스를 구하다보니 패턴이 존재할 것 같다는 예감이 들었고, DP문제라는 것을 감으로 알 수 있었다. 하지만 점화식을 찾는 것이 너무 어려워서 다른 블로그를 참고하였다. 먼저 모든 숫자는 1로만 채우는 방법이 존재하기 때문에 DP테이블을 1.. 2024. 9. 26.
[백준 1389번] 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389# 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결# 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임# 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람# 유저 중에서 케빈 베이컨의 수가 가장 작은 사람# 즉, 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합import sysfrom collections import dequeinput = sys.stdin.readlinen, m = map(int,input().split())graph = [set() for _ in range(n+1)]minimum = float("inf.. 2024. 9. 10.
[백준 6118번] 숨바꼭질 import sysfrom collections import dequeinput = sys.stdin.readline# 헛간의 개수는 N(2 maximum: answer = [v] maximum = depth elif depth == maximum: answer.append(v) for n in graph[v]: if not visited[n]: q.append((n,depth+1)) visited[n] = Truebfs()print(f"{min(answer)} {maximum} {len(answer)}") 본 문제는 N개의 노드와 .. 2024. 8. 6.
[백준 1647번] 도시 분할 계획 import sysinput = sys.stdin.readline# 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다.(양방향)# 각 길마다 길을 유지하는데 드는 유지비가 있다. # 임의의 두 집 사이에 경로가 항상 존재한다.# 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다.# 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.# 1. 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. # 2. 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.# 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.n, m = map(in.. 2024. 8. 1.
[백준 2234번] 성곽 https://www.acmicpc.net/problem/2234import sysfrom collections import dequeinput = sys.stdin.readline# 서 : 1# 북 : 2# 동 : 4# 남 : 8# 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로# 1.성에 있는 방의 개수# 2.가장 넓은 방의 넓이# 3.하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기# 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.dx, dy = [-1,1,0,0],[0,0,-1,1]n, m = map(int,input().split())visited = [[False]*n for _ in range(m)]area = [lis.. 2024. 7. 17.

티스토리툴바