전체 글
14502번-연구소
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근방법 1) 접근 사고 DFS + BFS 문제 였습니다. 알고리즘 과정은 1.입력값을 받고 난 board 배열에서 3개의 기둥을 설치한 뒤 2.바이러스들이 모두 퍼집니다.(BFS 알고리즘 활용) 3.이후에 남은 공간을 측정하여 최대값일 경우 갱신합니다. 4.이때 DFS를 통해서 모든 경우를 구해주면 됩니다. 2) 시간 복잡도 모든 경우를 탐색해야 하므로 O(n^2)입니다. 3) 배운 점 무난했던 구현 ..
14501번-퇴사
문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 접근방법 1) 접근 사고 상담을 할 것인지 안 할 것인지 두 개의 경우를 비교해주면 되는 문제였습니다. 구현 논리는 주석으로 자세하게 참조하였습니다. 2) 시간 복잡도 DP를 활용하여 O(logn)으로 해결이 가능합니다. 3) 배운 점 무난한 문제였던거 같습니다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #defin..
14500번-테트로미노
문제 https://www.acmicpc.net/status?user_id=skaguq4270&problem_id=14500&from_mine=1 채점 현황 www.acmicpc.net 접근방법 1) 접근 사고 문제에 보면 한 테트로미노가 가질수 있는 최대값을 물어보는 문제였습니다. 도형들의 길이가 4이기 때문에 각 좌표마다 DFS탐색을 통해 4번째 탐색이 되었을때의 합계의 값을 최대가 되게 비교해주면 되는 방법으로 해결하였습니다. 이 방법으로 문제를 해결하면 예외가 한 가지 존재하는데 'ㅗ' 도형일 경우 DFS 탐색을 통해 모든 경우를 탐색하는게 불가능합니다. 왜냐하면 튀어나온 부분으로 들어갔다가 다시 돌아와서 탐색이 DFS로는 불가능하기 때문입니다. 이 부분만 저는 따로 함수를 구현해서 예외처리 해주..