본문 바로가기

분류 전체보기

 (74)
[BOJ 13255] 동전 뒤집기 https://www.acmicpc.net/problem/13255 13255번: 동전 뒤집기 첫째 줄에 동전의 개수 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 K (1 ≤ K ≤ 50)이 주어진다. 셋째 줄에는 A[i] (1 ≤ A[i] ≤ N)가 주어진다. www.acmicpc.net Tag : dp, combinatorics 문제요약 N개의 동전 중 \(A_i\)개를 랜덤으로 골라 뒤집는 작업을 N번 반복한다. 이 때 앞면이 위인 동전 개수의 기댓값을 구하라. 풀이 확률 dp다. 주의할 점이 있다면 경우의 수를 dp의 정의로 잡고 쭉 구해놓고 답을 출력할 때만 표본을 나누면 오버플로우때문에 문제가 된다. (long double에도 안들어간다) 이걸로 30분정도를 맞왜틀했다... \(d..
[BOJ 13257] 생태학 https://www.acmicpc.net/problem/13257 13257번: 생태학 첫째 줄에 N, C, D, M이 주어진다. (1 ≤ N ≤ 20, 1 ≤ C ≤ 20, 1 ≤ D ≤ 5, 0 ≤ M ≤ N) www.acmicpc.net Tag : dp, combinatorics 문제요약 D일동안 N마리의 새 중에 C마리를 랜덤하게 고르고 이 중 측정기가 달려있지 않은 새에게 측정기를 붙인다. 초기상태에는 모두 측정기가 달려있지 않다. 이 때 D일 후 측정기가 달린 새가 M마리일 확률을 구하라. 풀이 전형적인 확률 dp이다. 왜 그랬는지는 모르겠는데 dp 정의를 확률로 안하고 경우의 수로 했다. 표본을 그때그때 나누냐 나중에 한번에 나누냐의 차이밖에 없긴한데 오버플로우가 날 수 있으니 주의할 필요..
[BOJ 1167] 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net Tag : tree dp 문제요약 트리에서 가장 먼 정점쌍을 찾고 거리를 출력해라. 풀이 두가지 풀이가 존재한다. 1. 탐색 두번 음수 가중치를 가진 간선이 없을 때 성립하는 풀이로 아무 정점에서나 한번 돌려서 가장 먼 점을 찾고 찾은 가장 먼점에서 또 가장 먼 점을 찾는 풀이이다. 위 그림을 보면 아무 정점에서나 먼점을 찾아도 그게 바로 지름의 한쪽 끝이 된다는걸 알 수 있다. ..
[BOJ 2912] 백설공주와 난쟁이 https://www.acmicpc.net/problem/2912 2912번: 백설공주와 난쟁이첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000) 둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다. 셋째 줄에는 사진www.acmicpc.netTag : random, mo's, merge sort tree 문제요약쿼리마다 구간의 크기/2 보다 많은 비중을 차지하는 색이 있으면 yes + 색을 출력하고 없으면 no를 출력하는 문제다. 풀이매우 다양한 풀이가 존재한다.머지소트트리, mo's, 랜덤... 등mo's는 \(O((N + M) \times N^{\frac{1}{2}} + M \times C)\)랜덤은..
[BOJ 17132] 두더지가 정보섬에 올라온 이유 https://www.acmicpc.net/problem/17132 17132번: 두더지가 정보섬에 올라온 이유 문제에 제시된 이동을 끝냈을 때, 두더지가 느끼는 만족도의 총합을 출력한다. www.acmicpc.net Tag : dsu 문제요약 트리 위의 모든 정점쌍에 대해 경로 위의 간선 중 최소 가중치를 더하는 문제다. 풀이 https://kim1109123.tistory.com/17 의 d번과 동일하고 너무 전형적인 dsu 문제다. 간선을 내림차순으로 정렬한 후 차례대로 이어주면 현재 간선이 최소인 모든 정점쌍을 구할 수 있다. 전체코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; using ll = long long; int N..
[BOJ 2251] 물통 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net Tag : bfs, implementation 문제요약 물통 A, B, C가 있고 초기에는 C물통만 가득찬 상태다. 물통의 물을 다른 물통으로 옮길 때는 한 물통이 비거나, 다른 물통이 가득찰 때까지 물을 붓는다. 이때 A는 비우고 C에 담을 수 있는 물의 양을 모두 구하라. 풀이 상태가 많아봤자 \(200^3\)개이고 전이를 \(O(1)\)에 할 수 있기 때문에 bfs를 돌리..
[BOJ 3568] 방정식 https://www.acmicpc.net/problem/3586 3586번: 방정식 방정식 f(x) = 0을 푸는 프로그램을 작성하시오. f(x)는 후위표기법으로 쓰여져 있으며, 숫자와 연산자 +, -, *, /, 그리고 변수 x로 이루어져 있다. x는 방정식에서 최대 한 번 등장한다. 예를 들어, 방 www.acmicpc.net Tag : implementation, string, stack 문제요약 후위표기식 형태로 식을 주고 해를 찾으라는 문제다. X는 한번이하로 주어진다. -> 일차식 vs 상수 vs -1차식 풀이 일단 후위표기법으로 준게 너무 다행이다. 중위표기법으로 줬으면 그냥 안풀지 않았을까? 후위표기법으로 주어진 식을 계산하는 방법은 간단하다. 1. 스택에 값들을 집어넣다가 연산자를 만나..
[BOJ 17082] 쿼리와 쿼리 https://www.acmicpc.net/problem/17082 17082번: 쿼리와 쿼리첫 쿼리 이후, 배열은 [-2, 1, 0, 2, -1] 이다. 쿼리 놀이를 [1,4], [2,2] 와 같이 하면 종이에는 [2, 1]이 적히게 되고, 이 중 최댓값은 2이다. 다른 방식으로 쿼리 놀이를 하더라도 종이에 적힌 최댓값을www.acmicpc.netTag : greedy 문제요약배열 L, R에서 각각 구간의 왼쪽 끝, 오른쪽 끝을 뽑아서 구간을 M개 만드는데 이때 max( 구간의 max )를 최소화 하는게 목표다. 지문에서 max( 구간의 max ) 이런 식으로 설명했는데 그냥 구간들에서 최대 뽑으라는 말이다. 풀이일단 반드시 포함되는 구간이 있다.L, R을 정렬했을 때 [L_i, R_i]들은 무슨 짓을..

티스토리툴바