본문 바로가기
반응형

시뮬레이션15

백준 14719번 빗물 - C++ 풀이 1. 각 열마다 고이는 빗물의 양을 구해 합친다. 2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다. 3. 그 중 더 낮은 블록 높이까지 빗물이 고이게 된다. 1. 각 열마다 고이는 빗물의 양을 구해 합친다. 각 열마다 고이는 빗물의 양을 구한 뒤 합치는 방식으로 전체 고이는 빗물의 양을 구해준다. 이때 양 끝 열(제일 왼쪽과 오른쪽)에는 절대 빗물이 고일 수 없다. 2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다. 빗물이 고이기 위해서는 그릇의 형태가 되어야 한다. 즉, 양쪽이 i열보다 더 높은 블록으로 막혀있어야 한다. (양 끝 열에는 절대 빗물이 고일 수 없는 이유이다.) 또한 그.. 2023. 7. 24.
백준 16954번 움직이는 미로 탈출 - C++ 풀이 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 시간이 지남에 따라 미로가 바뀌고 있으므로, 상태 노드를 나타내기 위해 필요한 값은 행, 열, 그리고 시간 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. BFS를 사용하여 시작 노드 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 언제 도착했는지는 상관이 없기 때문에 r=0, c=7인 노드인지만 확인하면 된다. #include #include using namespace std; typedef.. 2022. 9. 30.
백준 15685번 드래곤 커브 - C++ 풀이 1. 다음 세대 드래곤 커브를 만들 때는, 최근에 생성된 순서로 점들을 회전시킨다. 2. 주어진 드래곤 커브들을 시뮬레이션한 뒤 네 꼭짓점이 모두 드래곤 커브에 포함된 정사각형의 개수를 센다. 1. 다음 세대 드래곤 커브를 만들 때는, 최근에 생성된 순서로 점들을 회전시킨다. 드래곤 커브는 이루는 점들을 생성된 순서로 배열에 담는 것으로 나타낼 수 있다. 다음 세대 드래곤 커브는 현재 세대의 끝점(가장 최근에 생성된 점)을 기준으로 90도 회전하므로, 배열 역순으로 점들을 회전시켜준다. 2. 주어진 드래곤 커브들을 시뮬레이션한 뒤 네 꼭짓점이 모두 드래곤 커브에 포함된 정사각형의 개수를 센다. 1의 방법으로 주어지는 드래곤 커브들을 모두 시뮬레이션으로 생성한 뒤, 드래곤 커브에 속하는 좌표를 체크해 조건.. 2022. 8. 14.
백준 23290번 마법사 상어와 복제 - C++ 풀이 1. 각 단계를 시뮬레이션한다. 2. fish[x][y][d] = (x, y) 위치에서 d 방향을 향하는 물고기의 수의 형태로 물고기 정보를 관리한다. 1. 각 단계를 시뮬레이션한다. 단순 시뮬레이션 구현 문제라 특별한 알고리즘이나 자료구조가 필요하지는 않다. 다만 물고기의 수가 매우 많아질 수 있기 때문에 물고기를 1차원 배열로 관리하면 시간 초과를 맞을 수 있다. 2. fish[x][y][d] = (x, y) 위치에서 d 방향을 향하는 물고기의 수의 형태로 물고기 정보를 관리한다. 물고기의 상태는 위치와 방향으로 결정된다. 4x4칸, 8가지 방향이 있으므로 각 칸에서 각 방향을 향하고 있는 물고기의 수의 형태로 관리하면 시간을 줄일 수 있다. #include #include #include #incl.. 2022. 7. 28.
백준 18809번 Gaaaaaaaaaarden - C++ 풀이 1. 배양액을 뿌리는 모든 경우를 고려하여 피울 수 있는 꽃의 최대 개수를 찾는다. 2. BFS를 사용하여 배양액의 전이를 시뮬레이션한다. 1. 배양액을 뿌리는 모든 경우를 고려하여 피울 수 있는 꽃의 최대 개수를 찾는다. 배양액을 뿌릴 수 있는 땅의 개수가 최대 10개이고, 뿌려야 하는 배양액의 개수도 최대 10개이므로, 최대 배양액을 뿌리는 경우의 수는 최대 10C5 = 252가지 밖에 없다. 또한 각 경우를 O(N^2)에 시뮬레이션할 수 있으므로 브루트 포스를 사용해도 충분하다. 배양액을 뿌릴 곳을 선택할 때는 비트 마스킹을 사용하였다. 초록과 빨강 배양액을 뿌릴 곳을 각각 G, R개를 선택하고, 두 색깔이 겹치는 곳이 있는지 확인해주었다. 2. BFS를 사용하여 배양액의 전이를 시뮬레이션한다. 배.. 2022. 7. 27.
반응형

티스토리툴바