본문 바로가기

분류 전체보기

 (146)
[ BOJ 백준 3020번 - 개똥벌레 ] 해설 및 코드 https://www.acmicpc.net/problem/3020 목적 1에서 H의 높이로 동굴을 일직선으로 통과하는 동안에, 만나는 장애물의 최소 개수와 그 때의 경로의 개수를 구하자. 접근법 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 #include #define f(i,l,r) for(int i=l;i> n >> h; n /= 2; f(i, 0, n) { int a, b; cin >> a >> b; --s[a]; ++s[h - b]; } int mn = n, cnt = 1, curr=n; f(i, 1, h) { curr += s[i]; if (c..
[ BOJ 백준 1939번 - 중량제한 ] 해설 및 코드 https://www.acmicpc.net/problem/1939 목적 섬과 섬 사이에 중량제한 데이터가 주어질 때, 공장이 있는 섬을 연결하는 경로중에 중량제한이 가장 큰 경로를 구하자. 접근법 1. 이분탐색으로 중량을 구한 후, dfs나 bfs로 검증한다. 두 가지 방법으로 테스트해 보았다. 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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include #include #include #define f(i,l,r) for(int i=l;i>..
[ 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..

티스토리툴바