본문 바로가기

알고리즘74

[BFS] 백준 17141 : 연구소2 - 파이썬 Python https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 생각하기 연구소 전체를 점령할 수 있는 최소시간을 구하는 문제이므로 BFS를 통해 점령하다가 점령이 완료되면 그 때의 time을 min_time과 비교하면 되는 문제로 생각했다 바이러스를 놓을 수 있는 후보 여러 개중에서 M개를 선택하여 바이러스를 놓는다 -> 조합을 사용 처음에 모든 빈칸 + 바이러스 놓을 수 있는 후보지를 counting한 후 BFS 큐를 돌면서 counting을 차감해주는 방식으로 점.. 2022. 2. 17.
[DP] 백준 12869번 : 뮤탈리스트 - 파이썬 Python https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net DP문제는 내가 제일 어려워하는 유형이라 이 문제는 풀지 못하였다 백준 강의 앞부분에서 힌트를 얻고 풀어본 것을 써본다 생각하기 SCV의 값은 3이하로 매우 작다 각각의 SCV는 체력을 가지고 있다. DP[i][j][k] - SCV의 체력이 i, j, k 일때 모두 파괴하는 최소 공격횟수 SCV가 3마리라고 가정으로 하고 만약 2마리인 경우에는 DP[i][j][0]으로 처리해주면 된다 따라서 3차원 DP를.. 2022. 2. 16.
[구현] 백준 17143 : 낚시왕 - 파이썬 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 생각하기 상어의 정보 저장? 리스트에 각 상어의 r, c, s, d, z(위치, 크기, 방향, 속도)를 저장 shark[r][c] 는 (r,c)에 있는 상어 -> 상어의 위치가 변하고 위치가 중요하기 때문에 현재 문제에는 이러한 접근이 구현하기 편함 상어의 같은 위치에 여러마리 모든 상어를 이동 시키고 모든 칸을 살펴 보면서 2마리 이상이면 한마리로 -> 배열이 여러차원으로 형.. 2022. 2. 14.
[구현] 백준 16235 : 나무 재테크 - 파이썬 Python https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 생각하기 각 칸에 나무가 있고 봄, 여름, 가을, 겨울에 따라 각 칸에 대한 이벤트를 수행 시간복잡도 최대 1000년이므로 1000년동안 N*N의 칸을 돌아다닐 예정 N의 최대는 10이므로 100개의 칸을 돌아다닌다 각 칸에서는 최대 100개의 나무가 있을수 있다 1000 * 100 * 100 < 10^9이므로 충분히 시간 복잡도 안에 해결 가능 N, M, K = map(int, .. 2022. 2. 8.

티스토리툴바