본문 바로가기

백준28

[BFS] 백준 1600번 : 말이 되고픈 원숭이 - 파이썬 Python https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 생각하기 처음에는 말의 움직임과 원숭이 본래 움직임을 통합하여 BFS로 풀고자 하였다. 하지만 간과한 사안이 있었다. 말의 움직임과 원숭이 본래 움직임이 전혀 다른 패턴이기 때문에 원숭이의 본래 움직임으로 방문한 칸을 나중에 말의 움직임으로 더 짧은 시간에 방문할 수 있다는 점이었다. 만약 움직임의 패턴이 다른 경우, 칸까지 움직인 최소 거리를 하나의 visited 배열에 넣는 방.. 2022. 3. 10.
[구현] 백준 17140 : 이차워 배열과 연산 - 파이썬 Python https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net R 연산과 C 연산을 나누어서 생각했다 각 연산에서의 진행 과정은 아래와 같다 모든 row (R연산) 혹은 col (C연산)에 대해 각 수의 개수 카운팅 하면서 dictionary에 추가 dictionary를 tuple로 풀어서 sort (1 idx 우선, 2 idx 다음) sort된 튜플을 풀어서 새로운 A로 생성 col_cnt (C연산) 혹은 row_cnt (R연산)을 갱신 R,C.. 2022. 3. 7.
[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.

티스토리툴바