본문 바로가기
반응형

Problem Solving242

백준 1365번 꼬인 전깃줄 - C++(cpp) 풀이 1. 줄이 꼬이지 않으려면 연결된 오른쪽 전봇대들의 번호가 오름차순이어야 한다. 2. 잘라내는 전깃줄을 최소로 하려면, 남아있는 전깃줄을 최대로 하면 된다. 3. 가장 긴 증가하는 부분 수열의 길이만큼 남기는 것이 최대이다. 1. 줄이 꼬이지 않으려면 연결된 오른쪽 전봇대들의 번호가 오름차순이어야 한다. 왼쪽 i번 전봇대와 연결된 오른쪽 전봇대의 번호를 A[i]라고 하면, i A[j]이면 줄이 꼬이게 된다. 반대로 A[i] < A[j]이면 줄이 꼬이지 않는다. 따라서 줄이 꼬이지 않기 위해서는 연결된 오른쪽 전봇대들의 번호가 오름차순이어야 한다. 2. 잘라내는 전깃줄을 최소로 하려면, 남아있는 전깃줄을 최대로 하면 된다. 잘라내는 전깃줄을 최소로 하여 꼬인 부분이 없게 만들어야 .. 2022. 5. 9.
백준 2468번 안전 영역 - C++(cpp) 풀이 1. 물에 잠기지 않은 지역을 정점으로 생각하고 상하좌우로 인접한 정점을 간선으로 이었을 때, 그래프의 연결 요소가 곧 안전 영역이다. 2. 그래프의 연결 요소 개수는 모든 정점을 방문하기 위해 호출해야 하는 DFS/BFS 횟수와 같다. 3. 가능한 모든 높이에 대해 해당 높이만큼 물이 찼을 때 안전영역의 개수를 센 뒤, 최댓값을 찾는다. 1. 물에 잠기지 않은 지역을 정점으로 생각하고 상하좌우로 인접한 정점을 간선으로 이었을 때, 그래프의 연결 요소가 곧 안전 영역이다. 주어진 상황을 그래프로 바꾸어 생각할 수 있다. 물에 잠기지 않은 지역을 정점으로 생각하고, 상하좌우로 인접한 정점들을 간선으로 이었을 때, 안전 영역은 그래프의 연결 요소와 같다. 2. 그래프의 연결 요소 개수는 모든 정점을 방문하기.. 2022. 5. 8.
백준 4963번 섬의 개수 - C++(cpp) 풀이 1. 땅인 칸을 정점으로 생각하고, 가로, 세로, 대각선으로 이어져있는 땅들을 간선으로 잇는다. 2. 하나의 섬은 그래프의 연결 요소 하나와 대응된다. 3. DFS/BFS를 사용해 그래프의 연결 요소 개수를 센다. 1. 땅인 칸을 정점으로 생각하고, 가로, 세로, 대각선으로 이어져있는 땅들을 간선으로 잇는다. 주어진 상황을 그래프로 바꾸어 생각할 수 있다. 땅인 칸을 정점으로, 이어져있는 땅들을 간선으로 이으면 그래프가 된다. 2. 하나의 섬은 그래프의 연결 요소 하나와 대응된다. 이제 섬은 그래프의 연결 요소와 같다는 것을 알 수 있다. 3. DFS/BFS를 사용해 그래프의 연결 요소 개수를 센다. 따라서 섬의 개수는 곧 그래프의 연결 요소 개수와 같다. 한 번의 DFS/BFS로 하나의 연결 요소에 속.. 2022. 5. 3.
백준 11055번 가장 큰 증가 부분 수열 - C++(cpp) 풀이 1. dp(idx): idx번째 수로 시작하는 합이 가장 큰 증가 부분 수열의 합 2. dp(idx) = max(arr[idx] + dp(next)) (단, idx < next이고 arr[idx] < arr[next]) 3. dp(i)의 최댓값이 합이 가장 큰 증가 부분 수열의 합이다. 1. dp(idx): idx번째 수로 시작하는 합이 가장 큰 증가 부분 수열의 합 dp(idx)를 idx번째 수로 시작하는, 합이 가장 큰 증가 부분 수열의 합이라고 하자. 2. dp(idx) = max(arr[idx] + dp(next)) (단, idx < next이고 arr[idx] < arr[next]) arr[idx] 뒤에는 arr[idx]보다 더 뒤에있으면서 큰 수만 올 수 있으므로 dp(idx) = idx < .. 2022. 5. 3.
백준 10819번 차이를 최대로 - C++(cpp) 풀이 1. N개의 정수의 순서를 정하는 경우의 수는 N! 2. N이 작으므로 모든 경우를 탐색하여 주어진 식이 최대가 되는 경우를 찾는다. 1. N개의 정수의 순서를 정하는 경우의 수는 N! 크기가 N인 배열에 들어있는 수들의 순서를 바꾸는 경우의 수는 N!이다. 2. N이 작으므로 모든 경우를 탐색하여 주어진 식이 최대가 되는 경우를 찾는다. N이 최대 8이므로 8! = 40,320가지밖에 되지 않는다. 따라서 시간 내에 모두 탐색하는 것이 가능하다. 재귀와 비트 마스크를 이용해서 모든 경우를 탐색하고 최대가 되는 경우를 찾으면 된다. #include #include #include using namespace std; int N; int arr[8], pick[8]; int brute_force(int i.. 2022. 5. 3.
반응형

티스토리툴바