반응형 Problem Solving/BOJ228 백준 4179번 불! - C++ 풀이 1. 각 칸에 불이 번지는 시각을 BFS로 시뮬레이션하여 구해둔다. 2. 지훈이의 이동을 BFS로 시뮬레이션한다. 1. 각 칸에 불이 번지는 시각을 BFS로 시뮬레이션하여 구해둔다. 불이 매 초마다 상하좌우로 한 칸씩 퍼져나가므로, BFS를 이용하여 시뮬레이션 할 수 있다. 각 칸에 불이 번지는 시각을 구해두자. 이는 최초 불로부터의 거리와 같다. 2. 지훈이의 이동을 BFS로 시뮬레이션한다. 지훈이 또한 매 초마다 상하좌우로 이동할 수 있으므로, BFS를 이용하여 시뮬레이션 할 수 있다. 지훈이가 각 칸에 도착하는 시각 또한 최초 위치에서의 거리와 같다. 따라서 이제 지훈이가 특정 칸에 도착하는 시각과 그 칸에 불이 번지는 시각을 비교하면, 불이 번지기 전에 특정 칸에 도착했는지를 알 수 있다. 불이 .. 2023. 8. 10. 백준 1890번 점프 - C++ 풀이 1. dp[r][c] : (r, c)에서 도착지점까지 가는 경로의 수 2. dp[r][c] = dp[r + board[r][c]][c] + dp[r][c + board[r][c]] 1. dp[r][c] : (r, c)에서 도착지점까지 가는 경로의 수 dp[r][c]를 위와 같이 정의하자. 기저사례는 도착지점인 경우가 되겠다. 2. dp[r][c] = dp[r + board[r][c]][c] + dp[r][c + board[r][c]] 각 칸에서 board[r][c]만큼 아래쪽으로 가는 방법과 오른쪽으로 가는 방법이 있으므로 이 두가지 방법으로 이동했을 때의 경로의 수를 더해주면 된다. 이때 점프 거리가 보드 밖으로 넘어가지 않는지 체크해주어야 하고, 만약 board[r][c] = 0인 경우 그 자리에서 .. 2023. 8. 9. 백준 1406번 에디터 - C++ 풀이 1. 모든 쿼리는 커서를 기준으로 이루어진다. 2. 커서보다 왼쪽에 있는 문자들과 오른쪽에 있는 문자들을 각각 스택으로 관리한다. 1. 모든 쿼리는 커서를 기준으로 이루어진다. 포인트는 모든 쿼리가 커서를 기준으로 이루어진다는 것이다. 2. 커서보다 왼쪽에 있는 문자들과 오른쪽에 있는 문자들을 각각 스택으로 관리한다. 따라서 커서 직전, 직후 문자들만 쿼리 대상이다. 이에 적합한 자료구조인 스택을 사용한다. 커서보다 왼쪽에 있는 문자들을 한 스택에 모아두고, 커서보다 오른쪽에 있는 문자들을 또 다른 스택으로 묶어 관리한다. 접근 가능한 top이 커서 쪽이 되는 순서로 저장해야 한다. 그러면 이제 모든 쿼리를 간단하게 구현할 수 있다. 왼쪽, 오른쪽 문자들이 담긴 스택을 각각 lst, rst라 하자. L:.. 2023. 8. 9. 백준 3079번 입국심사 - C++ 풀이 1. t초동안 심사할 수 있는 사람 수의 최댓값은 ∑(t / Tk)이다. 2. 파라매트릭 서치를 사용하여 M명을 모두 처리할 수 있는 최소 시간을 구한다. 1. t초동안 심사할 수 있는 사람 수의 최댓값은 ∑(t / Tk)이다. t초동안 심사할 수 있는 사람 수를 최대로 하려면, 각 심사대가 쉬지 않고 일을 해야 한다. 따라서 각 심사대가 t / Tk명을 처리할 수 있고 이를 모두 더하면 t초 동안 심사할 수 있는 사람의 수의 최댓값을 구할 수 있다. 시간복잡도는 O(N). 2. 파라매트릭 서치를 사용하여 M명을 모두 처리할 수 있는 최소 시간을 구한다. M명을 모두 처리할 수 있는 최소 시간을 min_t라고 하면, t >= min_t인 경우 항상 모든 사람 심사가 가능하고 t < min_t인 경우 항상.. 2023. 8. 5. 백준 15665번 N과 M (11) - C++ 풀이 1. 숫자를 하나씩 총 M개 뽑는다. 2. 숫자를 뽑을 때는 작은 숫자부터 뽑아본다. 3. 후보 숫자 목록에 중복이 없도록 후보 숫자들을 배열이 아닌 set으로 관리한다. 1. 숫자를 하나씩 총 M개 뽑는다. N개의 후보 숫자 중에서 총 M개 뽑으면 수열이 완성된다. M개를 다 뽑았으면 완성된 수열을 출력해주는 것을 반복한다. 2. 숫자를 뽑을 때는 작은 숫자부터 뽑아본다. 수열을 사전 순으로 증가하는 순서로 완성해야 한다. 따라서 뽑을 때 더 작은 숫자를 먼저 뽑아야 한다. (0으로 시작하는 수열을 1로 시작하는 수열보다 먼저 출력해야 하므로 0부터 뽑아보는 것이다.) 3. 후보 숫자 목록에 중복이 없도록 후보 숫자들을 배열이 아닌 set으로 관리한다. 그런데 중복되는 수열을 출력하면 안된다. 중복되는.. 2023. 8. 3. 이전 1 2 3 4 5 ··· 46 다음 반응형
