본문 바로가기
반응형

Problem Solving/BOJ228

백준 2650번 교차점개수 - C++(cpp) 풀이 1. 세 개 이상의 연결선이 한 점에서 만나지 않으므로, 교차하는 선분 쌍의 개수가 곧 교차점의 개수이다. 2. 한 선분이 다른 선분을 완전히 포함하는 경우에는, 교차하지 않는 것으로 판정한다. 3. 모든 선분 쌍에 대해 교차 여부를 구하면서 총 교차점 수와 최대 교차점 수를 구한다. 1. 세 개 이상의 연결선이 한 점에서 만나지 않으므로, 교차하는 선분 쌍의 개수가 곧 교차점의 개수이다. 두 점을 직선으로만 잇는다면 세 개의 선분 A, B, C가 한 점에서 만날 수 있다. 이때 선분 쌍 AB, BC, 그리고 CA가 교차한다. 그런데 세 개 이상의 선분을 한 점에서 만나도록 하면 안 된다. 즉 각 선분 쌍이 모두 다른 점에서 만나도록 해야 하므로, 선분 쌍의 개수가 곧 교차점의 개수와 같게 된다. 2. .. 2022. 4. 7.
백준 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.
반응형

티스토리툴바