본문 바로가기

Problem Solving/BOJ 백준

 (132)
[ BOJ 백준 11437번 - LCA ] 해설 및 코드 https://www.acmicpc.net/problem/11437 목적 트리에서 두 정점이 주어질 때, 최소 공통 조상을 찾자. 접근법 1. 트리에서 정점의 부모와 깊이를 배열에 저장하고, 입력으로 주어지는 정점의 깊이를 동일하게 한 뒤, 동시에 위로 올라가면서 부모가 같은지 비교한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include #define f(i,l,r) for(int i=l;i>n; while(--n){ int a,b;cin>>a>>b; m[a].push_back(b); m[b].push_back(a); } t[..
[ BOJ 백준 16434번 - 드래곤 앤 던전 ] 해설 및 코드 https://www.acmicpc.net/problem/16434 목적 던전의 모든 용을 쓰러뜨리기 위한 용사의 최대 체력을 구하자. 접근법 1. 이분 탐색으로 푼 사람들도 많지만, 이 문제는 구현문제다. 그냥 O(n)의 시간복잡도로 풀자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include using namespace std; typedef long long ll; int main(){ ios_base::sync_with_stdio(false);cin.tie(0); ll n,atk;cin>>n>>atk; ll curr=0, mx=0; while(n--){ int t,a,h; cin>>t>>a>>h; if(t=..
[ BOJ 백준 3649번 - 로봇 프로젝트 ] 해설 및 코드 https://www.acmicpc.net/problem/3649 목적 구멍을 막을 수 있는 차이의 절대값이 가장 큰 조각 2개를 찾자. 접근법 1. 정렬 후 투포인터 알고리즘으로 양쪽 끝에서 조건을 만족하는 조각을 찾아나간다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include #define f(i,l,r) for(int i=l;i>n; int a[(int)1e6];f(i,0,n)cin>>a[i]; sort(a,a+n); int l=0,r=n-1; while(l
[ BOJ 백준 3056번 - 007 ] 해설 및 코드 https://www.acmicpc.net/problem/3056 목적 n명의 요원과 각 요원의 미션별 성공 확률이 주어질 때, 미션당 요원을 한명씩 배치하여 모든 미션을 수행할 때, 가장 높은 성공 확률을 구하자. 접근법 1. 완전 탐색 알고리즘을 구현해야 하며, 비트마스크를 이용해서 접근한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include #include #define f(i,l,r) for(int i=l;i>a[i][j]; cout.precision(6); cout
[ BOJ 백준 3980번 - 선발 명단 ] 해설 및 코드 https://www.acmicpc.net/problem/3980 목적 11명의 선수의 포지션 별 능력치가 주어지고, 각 포지션에 배치했을 때 능력치의 최대합을 구하자. 접근법 1. DFS 완전탐색으로 접근하자. 2. 포지션에 능력치가 0인 선수는 배치 불가하니 이에 대한 처리를 해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include #include #define f(i,l,r) for(int i=l;i
[ BOJ 백준 3090번 - 차이를 최소로 ] 해설 및 코드 https://www.acmicpc.net/problem/3090 목적 자연수 N개로 이루어진 배열 A에서, 감소시키는 연산을 최대 T번 할때, 인접한 수의 차이의 최댓값을 최소로 만들자. 접근법 1. 0부터 10^9까지의 범위에서 이분탐색으로 인접한 수의 차이 값의 상한을 구해나간다. 2. 상한값을 정했다면, 인접한 두 수의 차이를 상한값 이하로 만들어줘야한다. 여기서 중요한 점은 행렬을 정방향, 역방향으로 한번씩 순회하면서, 진행 방향으로 나보다 큰 앞 놈만 쳐내야 한다. (정방향으로 진행하던 도중에 나보다 큰 뒷 놈이 신경쓰여 역방향으로 쳐내며 진행하다보면 시간초과를 경험할 것이다.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..
[ BOJ 백준 15732번 - 도토리 숨기기 ] 해설 및 코드 https://www.acmicpc.net/problem/15732 목적 규칙에 맞게 앞에서 부터 도토리를 집어넣었을 경우, 가장 마지막 도토리가 들어가게 될 상지가 어떤건지 구하자. 접근법 1. 규칙에 맞게 다 집어 넣고 답을 구하기에는 일단 집어 넣다가 시간초과에 걸리고 만다. (입력이 상자 100만개, 규칙 만개, 각 규칙 당 C가 1일 경우 10^10의 시간복잡도가 나오므로...) 2. 하나의 방법은 백만개의 상자를 만져서 시간 복잡도를 줄여야 한다. 바로 이분탐색이다. 1부터 백만까지를 범위로 적정 값을 이분탐색해야 한다. (이렇게 하면 20*10^4 정도 되려나..) 3. i번 상자까지 총 몇개의 도토리를 집어 넣었는지는 ... 간단한 수학이다. 1 2 3 4 5 6 7 8 9 10 11 12..
[ BOJ 백준 2585번 - 경비행기 ] 해설 및 코드 https://www.acmicpc.net/problem/2585 목적 다음 그림과 같이 S(=출발지: {0,0}), T(=도착지: {10000,10000}), 그리고 N개의 경유지가 있는데, M번을 경유하여 S에서 T로 가기위해 필요한 연료통의 최소 용량을 구하자. 접근법 1. 연료통의 용량을 1에서 S에서 T까지 가는데 필요한 양까지를 범위로 하는 이분탐색 알고리즘을 적용한다. 2. 제곱근을 구하는 오버헤드가 어느정도 존재하므로, 이 연산은 생략하고 진행한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #define DIST(a,b,c,d) ((a..

티스토리툴바