본문 바로가기

알고리즘 문제147

[알고리즘 문제] 백준14719 - 빗물 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치� www.acmicpc.net 예전에 모 회사 코딩테스트에 나왔던 문제인데 그떄 못풀었습니다. 어떻게풀까 고민만 하다가 끝난 문제... 해결방법은 각열에 빗방울을 떨어뜨려보면서 넘치지 않으면 정답에 더해주었습니다. 여기서 넘치지 않는것을 검사하는 방법은 각 열의 좌우로 빗방울의 높이보다 같거나 더 높은 벽이 있으면 됩니다. 그리고 빗방울을 하나씩 더해주는 것보다 각 열에서 높이가 넘치지 않을 정도의 최대높이부터 하나씩 빼.. 2020. 9. 9.
[알고리즘 문제] 백준3055 - 탈출 www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제�� www.acmicpc.net 물을 먼저 퍼뜨리고 이후에 고슴도치를 움직이는 방식으로 풀 수 있습니다. 그리고 고슴도치의 중복동선과 최단시간은 visited[][]로 관리할 수 있습니다. 전형적인 bfs문제입니다. #include #include using namespace std; int height, width; pair des, start; queue mole, water; int visited[50][50]; string map[50]; in.. 2020. 9. 8.
[알고리즘 문제] 백준15686 - 치킨 배달 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨 가게중 M개를 선정하고 모두 선정했다면 각 집에서 치킨집과의 최단 거리를 구합니다. 여기서 M개의 가게를 선정할 때는 재귀를 사용하였고 선정한 가게는 visited[]에 체크해 주었습니다. #include #include #include #include using namespace std; const int MAX = 51; vector ck; vector homes; vector c.. 2020. 9. 8.
[알고리즘 문제] 백준1034 - 램프 www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져� www.acmicpc.net 처음에 재귀로 풀었다가 시간초과가 나왔습니다. 재귀를 이용해서 몇가지 방법으로 풀어봤는데 계속 시간초과가 나와서 다른 사람의 풀이를 참고하였습니다. 문제에서 구하는 값은 모든 열이 켜져있는 행의 최대개수를 구하는 문제입니다. 여기서 중요한 것은 모든 열이 켜져있어야 합니다. 대신에 키고/끄고할 수 있는 기준은 "열"입니다. 여기서 생각해볼 수 있는 점은 1행의 전구패턴과 2행의 전구패턴이 같다면 1행의.. 2020. 9. 6.

티스토리툴바