본문 바로가기
반응형

Problem Solving/BOJ228

백준 1701번 Cubeditor - C++(cpp) 풀이 1. dp(a, b): 가장 길게 일치하는 부분 문자열 S[a...], S[b...]의 길이 2. S[a] == S[b] 인 경우 dp(a, b) = 1 + dp(a+1, b+1) 3. S[a] != S[b]인 경우 dp(a, b) = 0 1. dp(a, b): 가장 길게 일치하는 부분 문자열 S[a...], S[b...]의 길이 2번 이상만 등장하면 되므로, 서로 다른 시작점 2개가 있으면 된다. 따라서 dp(a, b)를 위와 같이 정의하자. 2. S[a] == S[b] 인 경우 dp(a, b) = 1 + dp(a+1, b+1) S[a] == S[b]인 경우, 첫 글자가 일치하므로 1+ dp(a+1, b+1)이 된다. 3. S[a] != S[b]인 경우 dp(a, b) = 0 첫 글자부터 일치하지 않는.. 2022. 5. 12.
백준 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.
반응형

티스토리툴바