본문 바로가기
반응형

알고리즘115

BOJ 14502 - 연구소 / C++ 문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 벽 3개를 세울 수 있는 경우의 수는 DFS로 완전탐색하고 그렇게 생성된 배열을 다시 BFS로 순회하며 바이러스를 퍼뜨리고 안전 영역을 세야한다. 우선, 입력 받은 배열을 돌며 0(빈 칸)을 발견하면 해당 지역부터 DFS를 시작한다. 해당 지역에 벽(1)을 세우고 DFS 카운트를 늘려준 뒤 다시 배열을 돌며 다음 0(빈 칸)을 찾는다. 이렇게 DFS의 카운트가 3이 되면 벽을 모두 세웠으므.. 2022. 5. 4.
BOJ 14501 - 퇴사 / C++ 문제 링크 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 문제의 형태 덕분에 DP로 풀이해야한다는 것은 쉽게 감이 오지만 점화식을 세우기는 어렵다. 먼저 i일에 할 수 있는 행동을 생각해보면 1. Ti 만큼의 날짜를 소요하여 Pi를 획득한다. 2. 그냥 i+1로 건너뛴다. 1번 경우에는 DP[i + Ti] + P[i] = DP[i]가 될 것이고 2번 경우에는 DP[i + 1] = DP[i]이 될 것이다. 따라서, DP[i]에 대한 점화식을 DP[i] = max(DP[i + Ti] + P[i], DP[i + 1])로 세울 수 있다. 하지만, 이렇게 점화식을 세우려면 DP[.. 2022. 5. 4.
BOJ 14500 - 테트로미노 / C++ 문제 링크 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 보라색 모양 블록(ㅗ, ㅜ, ㅏ, ㅓ)를 제외하고는 모두 DFS로 순회할 수 있다. 따라서, DFS로 순회하며 Depth가 0부터 시작하여 3일 때 멈추고 answer값을 최댓값으로 갱신해준다. 보라색 모양의 블록은 4가지 경우를 모두 직접 구현해야한다. 단순 좌표 계산만 하면 되므로 그렇게 어렵지 않다. 모든 좌표를 돌며 answer값을 최댓값으로 갱신하고 출력해주면 된다. .. 2022. 5. 2.
BOJ 5430 - AC / C++ 문제 링크 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 입출력 방식이 독특해서 처리해야할 과정이 조금 존재한다. 숫자 배열을 입력받을 때 "[1, 2, 3, 4]"와 같이 들어오므로 char 형식의 변수를 하나 생성하여 괄호와 쉼표를 입력받고 사용하지 않는다. n == 0일 경우 괄호만 들어오므로 이 부분도 처리해야한다. 입력 처리가 완료되었으면 주어진 숫자들을 덱에 넣고 R, D 조건에 맞춰 구현하면 된다. 이 때, R이 들어올 때마다 원소들을 실제로 뒤집으면 시간 초과가 발생한다. 따.. 2022. 5. 1.
반응형

티스토리툴바