본문 바로가기
반응형

Problem Solving242

백준 5557번 1학년 - C++(cpp) 풀이 1. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수~마지막 수까지 고려할 때 만들 수 있는 등식의 수라고 하자. 2. dp(val, idx) = dp(val+arr[idx], idx+1) + dp(val-arr[idx], idx+1) 이다. 3. 최종적으로 구해야하는 값은 dp(arr[0], 1)이다. 1. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수~마지막 수까지 고려할 때 만들 수 있는 등식의 수라고 하자. 백트래킹으로 풀이하게되면, 최대 2^98번을 탐색하므로 시간초과가 발생한다. 중간 계산값이 0 이상 20 이하로 제한되어 있으므로 DP를 이용해서 풀이할 수 있다. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수부터 고려할 때 .. 2022. 4. 6.
백준 1405번 미친 로봇 - C++(cpp) 풀이 1. DFS로 모든 경우 4^N가지를 다 고려한다. 2. N칸 모두 이동했을 경우 해당 루트로 이동할 확률을 더한다. 1. DFS로 모든 경우 4^N가지를 다 고려한다. N이 작기 때문에 모든 경우를 다 고려하는 방법을 생각해볼 수 있다. N=14이므로 모든 경우의 수는 4^14 = 268,435,456이 된다. 중간에 방문했던 곳을 또 방문했을 경우 가지치기가 되므로 실제 탐색 횟수는 이것보다 더 적어진다. 2. N칸 모두 이동했을 경우 해당 루트로 이동할 확률을 더한다. N칸을 이동했을 때 해당 루트로 이동할 확률은 매 이동마다 해당 방향으로 이동할 확률의 곱과 같다. dfs에서 매 depth마다 이동 확률을 누적해서 전달해주면 된다. #include #include #include using nam.. 2022. 4. 5.
백준 1041번 주사위 - C++(cpp) 풀이 1. 3면이 노출되는 주사위는 4개, 2면이 노출되는 주사위는 (8*N-12) 개, 나머지는 1면만 노출되는 주사위이다. 2. 노출되는 면의 숫자 합이 최소가 되도록 한다. 3. N=1인 경우 예외 처리를 해준다. 1. 3면이 노출되는 주사위는 4개, 2면이 노출되는 주사위는 (8*N-12) 개,나머지는 1면만 노출되는 주사위이다. 윗면의 네 꼭짓점에 위치한 주사위는 세 면이 노출된다. 그리고 8개의 모서리에서 꼭짓점을 제외한 곳에 위치한 주사위들은 총 두 면이 노출된다. 나머지 주사위들은 한 면만 노출된다. 2. 노출되는 면의 숫자 합이 최소가 되도록 한다. 먼저 3면이 노출되는 주사위부터 생각해보자. 노출되는 3면의 종류는 꼭짓점의 개수와 같으므로 8가지이다. (AED, ABD, ACE, ABC, F.. 2022. 4. 4.
백준 22968번 균형 - C++(cpp) 풀이 1. f(h) = 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값이라고 하자. 2. 노드 수를 최대한 줄이기 위해서는 두 자식 트리의 높이를 각각 h-1, h-2로 만들어주어야 하므로 f(h) = f(h-1) + f(h-2) + 1 3. f(h) ≤ V인 h 중 최댓값을 찾는다. 1. f(h) = 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값이라고 하자. AVL 트리에서는 모든 부분 트리가 AVL 트리이다. 따라서 재귀적인 방법을 떠올릴 수 있다. 먼저 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값을 f(h)라고 정의하자. 2. 노드 수를 최대한 줄이기 위해서는 두 자식 트리의 높이를 각각 h-1, h-2로 만들어주어야 하므로 f(h) = f(h-.. 2022. 4. 1.
백준 1103번 게임 - C++(cpp) 풀이 1. 그래프에 사이클이 존재하면 무한번 움직일 수 있다. DFS를 이용해 사이클을 확인한다. 2. dp(r, c) = (r, c) 위치에서 시작했을 때 최대 이동 횟수라고 하면, dp(r, c) = 1 + max(dp(상), dp(하), dp(좌), dp(우)) 1. 그래프에 사이클이 존재하면 무한번 움직일 수 있다. DFS를 이용해 사이클을 확인한다. 무한번 움직일 수 있는 경우는, 그래프에 사이클이 존재하는 경우이다. DFS를 사용해서 사이클 존재여부를 체크한 후, 존재한다면 바로 -1을 출력해준다. 2. dp(r, c) = (r, c) 위치에서 시작했을 때 최대 이동 횟수라고 하면, dp(r, c) = 1 + max(dp(상), dp(하), dp(좌), dp(우)) dp(r, c) = (r,c) 위.. 2022. 3. 30.
반응형

티스토리툴바