본문 바로가기
반응형

Problem Solving242

백준 21611번 마법사 상어와 블리자드 - C++ 풀이 1. 블리자드 마법을 시뮬레이션한다. 2. 얼음 파편 던지기를 제외한 다른 작업은 1차원 배열로 변환하여 수행한다. 1. 블리자드 마법을 시뮬레이션한다. 단순 시뮬레이션 문제이다. 각 부분 작업을 잘 구현해주면 된다. 2. 얼음 파편 던지기를 제외한 다른 작업은 1차원 배열로 변환하여 수행한다. 맨 처음 얼음 파편 던지기 작업만 2차원 배열에서 수행한 뒤, 그 외 작업은 소용돌이 모양을 따라 1번 칸부터 마지막 칸까지를 1차원 배열로 바꾸어 작업해주면 구현이 편하다. 그리고 개별 구슬이 아닌 구슬 그룹 구조체로 관리해주면 더 편하게 작업을 구현할 수 있다. #include #include #include using namespace std; int N, M; int board[50][50]; int ex.. 2022. 7. 5.
백준 1981번 배열에서 이동 - C++ 풀이 1. 파라매트릭 서치를 이용하여 가장 작은 gap을 찾는다. 2. maxVal - minVal = gap이 되는 모든 (minVal, maxVal) 쌍에 대하여, (1,1)에서 출발하여 minVal 이상 maxVal 이하인 칸들로만 (n, n)에 도착할 수 있는지 여부를 DFS/BFS를 사용하여 구한다. 1. 파라매트릭 서치를 이용하여 가장 작은 gap을 찾는다. (최대-최소) = gap이라 하자. 가장 작은 gap을 구하는 최적화 문제이다. 이를 결정문제로 바꾸어 줄 것이다. decision(gap)을 최대값과 최소값의 차가 gap 이하가 되도록 할 수 있는가로 정의하고, 이분탐색을 이용하여 최초로 가능한 gap을 찾는다. 2. maxVal - minVal = gap이 되는 모든 (minVal, max.. 2022. 7. 4.
백준 1029번 그림 교환 - C++ 풀이 1. dp(curr, price, mask) = 현재 curr이 price원에 그림을 가지고 있고 지금까지 그림을 산 사람들이 mask일 때, 더 그림을 소유할 수 있는 사람 수의 최댓값 2. dp(curr, price, mask) = max(1, 1 + dp(next, nextPrice, newMask)) 1. dp(curr, price, mask) = 현재 curr이 price원에 그림을 가지고 있고 지금까지 그림을 산 사람들이 mask일 때, 더 그림을 소유할 수 있는 사람 수의 최댓값 dp(curr, price, mask)를 위와 같이 정의하자. 사람은 최대 15명, 가격은 최대 9원이므로 총 구해야 하는 dp값은 15*10*(2^15) 개. 2. dp(curr, price, mask) = max.. 2022. 7. 3.
백준 1162번 도로포장 - C++ 풀이 1. 다익스트라를 이용하여 1번 정점부터 N번 정점까지의 최소 거리를 구한다. 2. 다익스트라의 dist 배열을 포장 횟수까지 포함하여 운영한다. 3. 다익스트라 과정에서 간선을 포장하지 않는 경우와 포장하는 경우를 모두 고려한다. 1. 다익스트라를 이용하여 1번 정점부터 N번 정점까지의 최소 거리를 구한다. 두 정점의 최소 거리를 구하기 위해 다익스트라 알고리즘을 사용할 것이다. 2. 다익스트라의 dist 배열을 포장 횟수까지 포함하여 운영한다. 중간에 최대 K개의 간선의 가중치를 0으로 만들 수 있으므로, dist 배열을 포장 횟수까지 고려하여 2차원으로 운영한다. dist[idx][k] = 포장을 k번해서 1번 정점에서 idx번 정점으로 가는 최소 시간으로 정의할 수 있다. 3. 다익스트라 과정에서.. 2022. 7. 1.
백준 1450번 냅색문제 - C++ 풀이 1. 전체 물건을 두 그룹으로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해둔다. 2. A그룹에서 무게 w를 만들 수 있다면, B그룹에서 무게 C-w 이하를 만들 수 있어야 한다. 3. A그룹에서 만들 수 있는 모든 무게에 대해, 이분 탐색을 이용하여 B그룹에서 C-w이하를 만드는 조합의 수를 구한다. 1. 전체 물건을 두 그룹으로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해둔다. 모든 조합의 수는 2^N, N=30이므로 브루트 포스로는 제한시간 내에 통과할 수 없다. 이런 경우 두 그룹으로 쪼개 조합의 가짓수를 줄이는 방법을 사용할 수 있다. 두 그룹 A, B로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해두자. 이 과정의 시간복잡도는 O(2^N/2). 2. A그.. 2022. 7. 1.
반응형

티스토리툴바