본문 바로가기

분류 전체보기443

[백준 21609번] 상어 중학교 https://www.acmicpc.net/problem/21609# 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다.# 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현# 검은색 블록은 -1, 무지개 블록은 0으로 표현# 블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. # 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. # 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다.# 블록 그룹의 기준 블록은 무지개 블록이 아닌 .. 2024. 10. 1.
[백준 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.

티스토리툴바