본문 바로가기
반응형

전체 글282

백준 25197번 합주단 곰곰 - C++(cpp) 풀이 1. 두 곰곰이가 있을 때, 둘이 식사할 확률은 1/K 2. 곰곰이 두 마리를 고르는 경우의 수는 N*(N-1)/2 3. 따라서 식사 횟수의 기댓값은 N*(N-1)/2 * (1/K) 1. 두 곰곰이가 있을 때, 둘이 식사할 확률은 1/K 두 곰곰이가 있을 때, 둘이 식사하려면 같은 음을 골라야 한다. 둘이 같은 음을 고를 확률은 K/K^2 = 1/K이다. 2. 곰곰이 두 마리를 고르는 경우의 수는 N*(N-1)/2 또한 곰곰쌍은 총 N*(N-1)/2개 있다. 3. 따라서 식사 횟수의 기댓값은 N*(N-1)/2 * (1/K) 따라서 식사 횟수의 기댓값은 (곰곰쌍의 개수) * (곰곰쌍이 식사할 확률) = N(N-1)/2 * (1/K)이다. #include #include using namespace std;.. 2022. 5. 19.
백준 25174번 힘겨운 쿠기의 식당 개업기 - C++(cpp) 풀이 1. 좌표압축으로 x, y값 범위를 N이하로 줄인 뒤, 각 좌표에 고양이들의 Z값을 기록한 2차원 배열을 board를 만든다. 2. board의 누적합을 기록한 2차원 배열 psum을 만든다. 3. psum을 활용하여 4분면으로 나누는 모든 경우에 대해 E값을 구한 뒤 최솟값을 찾는다. 1. 좌표압축으로 x, y값 범위를 N이하로 줄인 뒤, 각 좌표에 고양이들의 Z값을 기록한 2차원 배열을 board를 만든다. 좌표평면에서 유의미한 포인트들은 고양이가 위치하는 포인트들이다. 유의미한 두 좌표값 사이의 무의미한 좌표값들은 모두 같은 결과를 만들어낸다. 좌표압축으로 x, y값의 범위를 줄여주자. 2. board의 누적합을 기록한 2차원 배열 psum을 만든다. i 사분면에 있는 Z값 합을 구하기 위해 누적합.. 2022. 5. 17.
백준 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.
반응형

티스토리툴바